Records of Turing machines

Front Cover
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).

From inside the book

What people are saying - Write a review

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

Common terms and phrases

Bibliographic information