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