1. Turing machines 13

algorithm were proposed (Turing machine, Post machine, Church’s lambda-

calculus, G¨ odel’s theory of recursive functions), but they all turned out to

be equivalent to each other. The reader can find a detailed exposition of the

theory of algorithms in [5, 39, 40, 48, 54, 60, 61].

We make some informal remarks about the capabilities of Turing ma-

chines. A Turing machine behaves like a person with a restricted memory,

pencil, eraser, and a notebook with an infinite number of pages. Pages are

of fixed size; therefore there are finitely many possible variants of filling a

page, and these variants can be considered as letters of the alphabet of a

TM. The person can work with one page at a time but can then move to the

previous or to the next page. When turning a page, the person has a finite

amount of information (corresponding to the state of the TM) in her head.

The input string is written on several first pages of the notebook (one

letter per page); the output should be written in a similar way. The com-

putation terminates when the notebook is closed (the head crosses the left

boundary) or when the person does not know what to do next (δ is unde-

fined).

Think about yourself in such a situation. It is easy to realize that by

memorizing a few letters near the head you can perform any action in a

fixed-size neighborhood of the head. You can also put extra information

(in addition to letters from the external alphabet) on pages. This means

that you extend the tape alphabet by taking the Cartesian product with

some other finite set that represents possible notes. You can leaf through

the notebook until you find a note that is needed. You can create a free cell

by moving all information along the tape. You can memorize symbols and

then copy them onto free pages of the notebook. Extra space on pages may

also be used to store auxiliary strings of arbitrary length (like the initial

word, they are written one symbol per page). These auxiliary strings can

be processed by “subroutines”. In particular, auxiliary strings can be used

to implement counters (integers that can be incremented and decremented).

Using counters, we can address a memory cell by its number, etc.

Note that in the definition of computability for functions of type

A∗

→

A∗

we restrict neither the number of auxiliary tape symbols (the set of

symbols S could be much bigger than A) nor the number of states. It

is easy to see, however, that one auxiliary symbol (the blank) is enough.

Indeed, we can represent each letter from S \ A by a combination of blanks

and nonblanks. (The details are left to the reader as an exercise.)

Since a Turing machine is a finite object (according to Definition 1.1),

it can be encoded by a string. (Note that Turing machines with arbitrary

numbers of states and alphabets of any size can be encoded by strings over a

fixed alphabet.) Then for any fixed alphabet A we can consider a universal