Records of Turing machines
Herbert S. Shank, Cornell University. Center for Applied Mathematics, United States. Air Force. Office of Scientific Research
Cornell University, Center for Applied Mathematics, 1968 - Computers - 20 pages
Suppose 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.
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