On the expressiveness of single-pass instruction sequences

Abstract

We perceive programs as single-pass instruction sequences. A single-pass instruction sequence under execution is considered to produce a behaviour to be controlled by some execution environment. Threads as considered in basic thread algebra model such behaviours. We show that all regular threads, i.e. threads that can only be in a finite number of states, can be produced by single-pass instruction sequences without jump instructions if use can be made of Boolean registers. We also show that, in the case where goto instructions are used instead of jump instructions, a bound to the number of labels restricts the expressiveness.

14 pages; error corrected, acknowledgement added; another error corrected, another acknowledgement added

References in corpus (9)

• Instruction sequences with indirect jumps
• Projection semantics for rigid loops
• Thread extraction for polyadic instruction sequences
• Interface groups and financial transfer architectures
• Program algebra with a jump-shift instruction
• Instruction sequences and non-uniform complexity theory
• Tuplix Calculus Specifications of Financial Transfer Networks
• Autosolvability of halting problem instances for instruction sequences
• Instruction sequences with dynamically instantiated instructions

Cited by in corpus (9)

• Instruction sequence processing operators
• Instruction sequences and non-uniform complexity theory
• Putting Instruction Sequences into Effect
• Instruction sequence based non-uniform complexity classes
• Instruction sequence expressions for the secure hash algorithm SHA-256
• Quantitative Expressiveness of Instruction Sequence Classes for Computation on Single Bit Registers
• Instruction sequence notations with probabilistic instructions
• Instruction sequences expressing multiplication algorithms
• Indirect jumps improve instruction sequence performance