Program Algebra for Turing-Machine Programs

Scientific Annals of Computer Science

article

J. A. Bergstra¹  C. A. Middelburg¹ 

[1] Informatics Institute, Faculty of Science, University of Amsterdam, Science Park 904

关键词: program algebra;    thread algebra;    model of computation;    Turing-machine program;    computability;    computational complexity.;   

DOI  :  10.7561/SACS.2019.2.113

来源: Alexandru Ioan Cuza University of Iasi

【 摘 要 】

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.

【 授权许可】

CC BY-ND