COSC 3410
        Assignment #6
     Due: Friday, Nov 12

1. Write a transition table for a Turing machine
which will take a tape containing consecutive 1's and
rewrite it to alternating 1's and 2's.

       e.g.      D 1 1 1 1 1 1 1 _ _ _ ...
   should become D 1 2 1 2 1 2 1 _ _ _ ...


2. Trace the following Turing machine from the
given starting configuration (I think it might run
about 50 steps):

    1                     <- read/write head in state 1
  D 1 1 1 1 1 _ _ _ ...   <- tape
  
  
                   symbol
state |   _   |   1   |   2   |   3   |   D
------+-------+-------+-------+-------+-------
  1   |       | 2/2/R |       |       |
  2   |       | 3/2/R |       | 6/3/R |
  3   | 7/3/R | 4/1/R |       | 3/3/R |
  4   | 5/3/L | 4/1/R |       | 4/3/R |
  5   |       | 5/1/L | 1/2/R | 5/3/L |
------+-------+-------+-------+-------+-------
  6   | 7/_/L |       |       | 6/3/R |
  7   | 7/_/L | halt  | 7/_/L | 8/_/L | halt
  8   |       | 9/1/R | 8/2/L | 8/3/L | 9/D/R
  9   |       |       | X/1/R |       |
  X   | 7/_/L |       | X/2/R | X/3/R |
  
Here I'm using D for the left end of tape symbol,
underscore ( _ ) for an empty square, and X for the
tenth state.


3. If we assume a tape with n 1's represents the
number n, what mathematical function does the
machine in problem 2 compute?