Accession Number : AD0682322

Title :   RECORDS OF TURING MACHINES,

Corporate Author : CORNELL UNIV ITHACA N Y CENTER FOR APPLIED MATHEMATICS

Personal Author(s) : Shank,Herbert S.

Report Date : OCT 1968

Pagination or Media Count : 16

Abstract : 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)

Descriptors :   (*DIGITAL COMPUTERS, RECORDS), AUTOMATA, SYMBOLS, THEOREMS

Subject Categories : Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE