Title: Program algebra for Turing-machine programs,
Abstract: This note 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 the Turing tapes provided by an execution
environment. This theory provides a setting for investigating issues relating
to computability and computational complexity that is more general than the
closely related Turing-machine models 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.