14 1. Classical Computation

Turing machine U. Its input is a pair ([M],x), where [M] is the encoding

of a machine M with external alphabet A, and x is a string over A. The

output of U is ϕM (x). Thus U computes the function u defined as follows:

u

(

[M],x

)

= ϕM (x).

This function is universal for the class of computable functions of type

A∗

→

A∗

in the following sense: for any computable function f :

A∗

→

A∗,

there exists some M such that u([M],x) = f(x) for all x ∈

A∗.

(The equality

actually means that either both u(M, x) and f(x) are undefined, or they are

defined and equal. Sometimes the notation u([M],x) f(x) is used to stress

that both expressions can be undefined.)

The existence of a universal machine U is a consequence of the Church-

Turing thesis since our description of Turing machines was algorithmic. But,

unlike the Church-Turing thesis, this is also a mathematical theorem: the

machine U can be constructed explicitly and proved to compute the function

u. The construction is straightforward but boring. It can be explained as

follows: the notebook begins with pages where instructions (i.e., [M]) are

written; the input string x follows the instructions. The universal machine

interprets the instructions in the following way: it marks the current page,

goes back to the beginning of the tape, finds the instruction that matches the

current state and the current symbol, then returns to the current page and

performs the action required. Actually, the situation is a bit more complex:

both the current state and the current symbol of M have to be represented

in U by several symbols on the tape (because the number of states of the

universal machine U is fixed whereas the alphabet and the number of states

of the simulated machine M are arbitrary). Therefore, we need subroutines

to move strings along the tape, compare them with instructions, etc.

1.4. Complexity classes. The computability of a function does not guar-

antee that we can compute it in practice: an algorithm computing it can

require too much time or space. So from the practical viewpoint we are

interested in effective algorithms.

The idea of an effective algorithm can be formalized in different ways,

leading to different complexity classes. Probably the most important is the

class of polynomial algorithms.

We say that a function f(n) is of polynomial growth if f(n) ≤

cnd

for some constants c, d and for all suﬃciently large n. (Notation: f(n) =

poly(n).)

Let B be the set {0, 1}. In the sequel we usually consider functions and

predicates defined on

B∗,

i.e., on binary strings.

Definition 1.4. A function F on

B∗

is computable in polynomial time if

there exists a Turing machine that computes it in time T(n) = poly(n),