On Algorithmic Equivalence of Instruction Sequences for Computing Bit String Functions

Article type: Research Article

Authors: Bergstra, J.A.^a | Middelburg, C.A.^{a; *}

Affiliations: [a] Informatics Institute, University of Amsterdam, Science Park 904, 1098 XH Amsterdam, the Netherlands. {J.A.Bergstra, C.A.Middelburg}@uva.nl

Note: [*] Address for correspondence: Informatics Institute, University of Amsterdam, Science Park 904, 1098 XH Amsterdam, the Netherlands.

Abstract: Every partial function from bit strings of a given length to bit strings of a possibly different given length can be computed by a finite instruction sequence that contains only instructions to set and get the content of Boolean registers, forward jump instructions, and a termination instruction. We look for an equivalence relation on instruction sequences of this kind that captures to a reasonable degree the intuitive notion that two instruction sequences express the same algorithm.

Keywords: structural algorithmic equivalence, structural computational equivalence, single-pass instruction sequence, bit string function

DOI: 10.3233/FI-2015-1219

Journal: Fundamenta Informaticae, vol. 138, no. 4, pp. 411-434, 2015