Hints for Homework 11
---------------------

1) (a) The doubly-circled state is the accept state.   The reject state and
all transitions into it are not shown.  The underscore character is
the blank.

Figuring out the language might take a little thought.   It might be
useful to do part (c) first, to get a sense of what the TM is doing.
Notice that the input alphabet only contains one character.

(c) That is, give a sequence of configurations from the start configuration
to an accept or reject one.

------------------------------

2) Use a multi-tape Turing machine.  One or more of the secondary
tapes can be used as counters.

Give your design in pseudo-code,e.g. as in the examples towards the
end of Sipser 3.1 (pp. 146-147).  Be sure to keep it easy to read, not
filled with low-level code details.   Think about producing something
that the undergraduate graders will find pleasant to read and easy
to understand.

------------------------------

3) This should not be hard.   The point is to help you understand what an
encoding of a Turing machine might look like.

------------------------------

4) 

(a) Not hard.  

(b) Give your design only at a high level, in pseudocode.  See comment
on problem (2) about pseudocode.  Don't get into a lot of nasty
technical details.  If it is more than 1.5 pages long, you definitely
have too much detail.

Feel free to use a multi-tape Turing machine to do the simulation.

The central part of your solution should be an algorithm for
storing the 2D locations on the a 1D tape.   The way you do this
storage will determine what's involved in moving left, right, up
and down.   

One option is to create a clever mapping from all 2D locations to the
1D locations.

Another approach is to store only the part of the 2D plan that's
currently in use.  For example, you might store a rectangular portion
of the plane that contains all the non-blank cells (and maybe some
blank cells).   Then expand the storage area when necessary.

You could also use a sparse array representation: store triples
(x,y,value) for each cell that contains something other than a blank.

Because there are many possible ways to store the 2D locations on the
tape, your solution should start by clearly describing which method
you are using.  Only after you've done that should you describe
details of how to operate the TM (e.g. move left).

Assume that we have subroutines to do simple arithmetic with unary or
binary numbers, shift a string rightwards to make more space, and
similar easy operations.