CS491 DESIGN PROBLEM D1
Due 9/30/02
Turing machines are basic models of computation. The Turing
Church thesis says that any procedure that can be described as
an algorithm can be carried out by a Turing machine. As part of
grounding your understanding of Turing machines, it is useful to
write a few Turing machine programs. A Turing machine program
can be represented as a series of lines of the form
i: L (t/t',j)
which means: when in state i, move Left, changing the current
symbol t to t', then enter state j. Instead of L, the move can
be R (right). If multiple transitions come from state i we
represent them as
i: L (t1/t1',j1),(t2/t2',j2),...,(tn/tn',jn)
The symbols t are all from a tape alphabet plus the blank (#)
symbol. By convention, we want a Turing machine to start with
its head positioned on the tape over the blank square just to
the left of the input; and when it stops, it is positioned on a
blank square just to the left of the output.
(1) Create a copier machine using this notation. Include a
description of the strategy followed by the machine. A copier
machine starts with a string S on its tape and stops with S#S
and the head positioned to the left of the second S. S is made of
binary symbols (0 and 1).
(2) Create an adder machine. This machine starts with S1#S2 and
finishes with S1#S2#S3, where S3 is the sum of S1 and S2. All
strings are in binary notation. Include a description of your
strategy.
(3) Create a doubler machine. This machine starts with S on the
tape and finishes with S#S1, where S1 is two times S. Hint:
combine the previous two machines.
(4) Construct your own version of Turing's argument that the
Halting Problem is not computable. If it were computable, there
would be a Turing machine H that starts with tape M#X (M =
description of another machine, X = description of its input
tape) and stops with tape #0# if M does not halt for X and #1#
if M halts for X. You want to show that the existence of H is a
contradiction. Why can't H simulate the action of M on X using
a universal-machine subroutine?
(5) Define a "multithreaded Turing machine" as a set of Turing
machines coordinated by a common finite-state controller. The
idea is that a computation can be divided into parallel pieces
and farmed out to independent Turing machines by the
controller; when those machines have all halted with their
results, the controller can combine the results together into a
single result on its tape. Does the multi-threading capability
add computational power to the Turing machine? That is, are
there multi-threaded computations that cannot be done by any
single-tape machine?