RECORDS OF TURING MACHINES,

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)

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1968
Accession Number
AD0682322

Entities

People

  • Herbert S. Shank

Organizations

  • Cornell University

Tags

DTIC Thesaurus Topics

  • Alphabets
  • Automata
  • Computations
  • Finite Alphabet
  • Machines
  • Mathematics
  • Sequences

Readers

  • Analytical Mechanics
  • Computer Programming and Software Development.
  • Computer Science/Computer Engineering/Data Science/Digital Signal Processing.