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 diﬃcult. 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-

nents:

– 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

Cells

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

http://dx.doi.org/10.1090/gsm/047/03