1. Turing machines 11
s , and the shift Δp (for example, Δp = −1 means that the head moves to
More formally, the configuration of a TM is a triple σ; p; q , where σ
is an infinite sequence s0,...,sn,... of elements of S, p is a nonnegative
integer, and q ∈ Q. At each step the TM changes its configuration σ; p; q
(a) it reads the symbol sp;
(b) it computes the value of the transition function: δ(q, sp) = (q , s , Δp)
(if δ(q, sp) is undefined, the TM stops);
(c) it writes the symbol s in cell p of the tape, moves the head by Δp, and
passes to state q . In other words, the new configuration of the TM is
the triple s0,...,sp−1,s , sp+1,... ; p+Δp; q . (If p + Δp 0, the TM
Perhaps everyone would agree that these actions require neither clever-
ness, nor imagination.
It remains to define how the input is given to the TM and how the result
is obtained. Inputs and outputs are strings over A. An input string α is
written on the tape and is padded by blanks. Initially the head is at the
left end of the tape; the initial state is q0. Thus the initial configuration is
α . . . ; 0; q0 . Subsequently, the configuration is transformed step by step
using the rules described above, and we get the sequence of configurations
α . . . ; 0; q0 , σ1; p1; q1 , σ2; p2; q2 , . . . .
As we have said, this process terminates if δ is undefined or the head bumps
into the (left) boundary of the tape (p + Δp 0). After that, we read
the tape from left to right (starting from the left end) until we reach some
symbol that does not belong to A. The string before that symbol will be
the output of the TM.
1.2. Computable functions and decidable predicates. Every Turing
machine M computes a partial function ϕM :
is the set
of all strings over A. By definition, ϕM (α) is the output string for input α.
The value ϕM (α) is undefined if the computation never terminates.
Definition 1.2. A partial function f from
is computable if there
exists a Turing machine M such that ϕM = f. In this case we say that f is
computed by M.
Not all functions are computable because the set of all functions of type
is uncountable, while the set of all Turing machines is countable.
For concrete examples of noncomputable functions see Problems 1.3–1.5.