10 1. Classical Computation
integer is represented by its remainders modulo different primes p1,p2,...,pn
(using the Chinese remainder theorem; see Theorem A.5 in Appendix A), it
is easy to multiply them, but comparison is more difficult. So we will specify
the encoding in case of doubt.
We now give a formal definition of an algorithm.
1.1. Definition of a Turing machine.
Definition 1.1. A Turing machine (TM) consists of the following compo-
a finite set S called the alphabet;
an element S (blank symbol);
a subset A S called the external alphabet; we assume that the blank
symbol does not belong to A;
a finite set Q whose elements are called states of the TM;
an initial state q0 Q;
a transition function, specifically, a partial function
δ : Q × S Q × S × {−1, 0, 1}. (1.1)
(The term “partial function” means that the domain of δ is actually a subset
of Q × S. A function that is defined everywhere is called total.)
Note that there are infinitely many Turing machines, each representing a
particular algorithm. Thus the above components are more like a computer
program. We now describe the “hardware” such programs run on.
A Turing machine has a tape that is divided into cells. Each cell carries
one symbol from the machine alphabet S. We assume that the tape is
infinite to the right. Therefore, the content of the tape is an infinite sequence
σ = s0,s1,... (where si S).
A Turing machine also has a read-write head that moves along the tape
and changes symbols: if we denote its position by p = 0, 1, 2,... , the head
can read the symbol sp and write another symbol in its place.
Position of head
s0 s1 . . . sp . . .
Cell numbers
0 1 p
The behavior of a Turing machine is determined by a control device,
which is a finite-state automaton. At each step of the computation this
device is in some state q Q. The state q and the symbol sp under the
head determine the action performed by the TM: the value of the transition
function, δ(q, sp) = (q , s , Δp), contains the new state q , the new symbol
Previous Page Next Page