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-
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
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