On algorithmic equivalence of instruction sequences for computing bit string functions

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.

27 pages, the preliminaries have textual overlaps with the preliminaries in arXiv:1308.0219 [cs.PL], arXiv:1312.1529 [cs.PL], and arXiv:1312.1812 [cs.PL]; 27 pages, three paragraphs about Milner's algorithmic equivalence hypothesis added to concluding remarks; 26 pages, several minor improvements of the presentation made

References in corpus (3)

• Program algebra with a jump-shift instruction
• Instruction sequence expressions for the secure hash algorithm SHA-256
• Long multiplication by instruction sequences with backward jump instructions

Cited by in corpus (9)

• On instruction sets for Boolean registers in program algebra
• Instruction sequence expressions for the secure hash algorithm SHA-256
• Instruction sequences expressing multiplication algorithms
• On the complexity of the correctness problem for non-zeroness test instruction sequences
• Long multiplication by instruction sequences with backward jump instructions
• Program algebra for Turing-machine programs
• On the formalization of the notion of an algorithm
• Program algebra for random access machine programs
• Intensional Constructed Numbers: Towards Formalizing the Notion of Algorithm