1. Turing machines 11

s , and the shift Δp (for example, Δp = −1 means that the head moves to

the left).

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

as follows:

(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

stops.)

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 :

A∗

→

A∗,

where

A∗

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

A∗

to

A∗

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

A∗

→

A∗

is uncountable, while the set of all Turing machines is countable.

For concrete examples of noncomputable functions see Problems 1.3–1.5.