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 sufficiently 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),
Previous Page Next Page