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?