## Records of Turing machinesSuppose a Turing machine is equipped with an extra tape. At each step of a computation being performed, it prints symbol read, move symbol, symbol printed on a square of the extra tape. It then moves the extra tape one square to the left. This procedure yields a record of the computation. If sigma is a finite alphabet, let sigma' be the set of triples a, b, c, where a epsilon sigma, c epsilon sigma, and b epsilon(-1,0,1). We will characterize those sequences of symbols of sigma' that are records of computations of Turing machines. (Author). |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Common terms and phrases

ABSTRACT Suppose AFOSR alphabet of quadruples alphabet of triples APPLIED MATHEMATICS Automata Theory Computation belongs to C(M characterize those sequences computation being performed computations of Turing CORNELL UNIVERSITY dimensional tapes directed graph equivalence classes extra tape family of sequences finite alphabet finite automaton finite sequences G-Turing initial segment belongs invariant equivalence relation KEY WORDS Lemma machine is equipped Machines Automata Theory machines that act minimal 0-sum segment move symbol symbol moves the extra NUMBER OF PAGES NUMBER OF REFERENCES obtain copies prints symbol read procedure yields PROJECT NUMBER pseudo-Turing machine R-consistent read move symbol reading head records of computations RECORDS OF TURING REPORT NUMBERS REPORT TITLE right-invariant equivalence relation sequences of elements sequences of symbols set of quintuples set of triples Suppose a Turing symbol read move symbol symbol printed tape one square Theorem TOTAL NUMBER transition function Turing Machines Automata Turing tape UNCLASSIFIED yields a record