Abstract
Instruction sequence is a key concept in practice, but it has as yet
not come prominently into the picture in theoretical circles.
This paper concerns instruction sequences, the behaviours produced by
them under execution, the interaction between these behaviours and
components of the execution environment, and two issues relating to
computability theory.
Positioning Turing's result regarding the undecidability of the halting
problem as a result about programs rather than machines, and taking
instruction sequences as programs, we analyse the autosolvability
requirement that a program of a certain kind must solve the halting
problem for all programs of that kind.
We present novel results concerning this autosolvability requirement.
The analysis is streamlined by using the notion of a functional unit,
which is an abstract state-based model of a machine.
In the case where the behaviours exhibited by a component of an
execution environment can be viewed as the behaviours of a machine in
its different states, the behaviours concerned are completely
determined by a functional unit.
The above-mentioned analysis involves functional units whose possible
states represent the possible contents of the tapes of Turing machines
with a particular tape alphabet.
We also investigate functional units whose possible states are the
natural numbers.
This investigation yields a novel computability result, viz. the
existence of a universal computable functional unit for natural
numbers.
View-only version of article
Preprint available:
arXiv:0910.5564 [cs.LO]