16 1. Classical Computation

[1] 1.2. Construct a Turing machine that adds two numbers written in

binary. (Assume that the numbers are separated by a special symbol “+”

that belongs to the external alphabet of the TM.)

[3!] 1.3 (“The halting problem is undecidable”). Prove that there is no algo-

rithm that determines, for given Turing machine and input string, whether

the machine terminates at that input or not.

[2] 1.4. Prove that there is no algorithm that enumerates all Turing ma-

chines that do not halt when started with the empty tape.

(Informally, enumeration is a process which produces one element of a set

after another so that every element is included in this list. Exact definition:

a set X ⊆

A∗

is called enumerable if it is the set of all possible outputs of

some Turing machine E.)

[3] 1.5. Let T(n) be the maximum number of steps performed by a Turing

machine with ≤ n states and ≤ n symbols before it terminates starting

with the empty tape. Prove that the function T(n) grows faster than any

computable total function b(n), i.e., limn→∞ T(n)/b(n) = ∞.

The mode of operation of Turing machines is rather limited and can be

extended in different ways. For example, one can consider multitape Turing

machines that have a finite number of tapes. Each tape has its own head

that can read and write symbols on the tape. There are two special tapes:

an input read-only tape, and an output write-only tape (after writing a

symbol the head moves to the right). A k-tape machine has an input tape,

an output tape, and k work tapes.

At each step the machine reads symbols on all of the tapes (except for

the output tape), and its action depends upon these symbols and the current

state. This action is determined by a transition function that says what the

next state is, what symbols should be written on each work tape, what

movement is prescribed for each head (except for the output one), and what

symbol should be written on the output tape (it is possible also that no

symbol is written; in this case the output head does not move).

Initially all work tapes are empty, and the input string is written on the

input tape. The output is the content of the output tape after the TM halts

(this happens when the transition function is undefined or when one of the

heads moves past the left end of its tape).

More tapes allow Turing machine to work faster; however, the difference

is not so great, as the following problems show.

[2] 1.6. Prove that a 2-tape Turing machine working in time T(n) for inputs

of length n can be simulated by an ordinary Turing machine working in time

O(T

2(n)).