Abstract
This paper presents an algebraic theory of instruction sequences with
instructions for Turing tapes as basic instructions, the behaviours
produced by the instruction sequences concerned under execution, and the
interaction between such behaviours and Turing tapes provided by an
execution environment.
This theory provides a setting for the development of theory in areas
such as computability and computational complexity that distinguishes
itself by offering the possibility of equational reasoning and being
more general than the setting provided by a known version of the
Turing-machine model of computation.
The theory is essentially an instantiation of a parameterized
algebraic theory which is the basis of a line of research in which
issues relating to a wide variety of subjects from computer science have
been rigorously investigated thinking in terms of instruction sequences.
Preprint available:
arXiv:1901.08840v2 [cs.PL]