Homework #8

1.  Design a Turing machine to recognize the language {ww^R:  w is in (0 v 1)*}.

2.  Show the sequence of configurations when processing the input
    001100 on the machine from problem 1.

3.  Design a Turing machine to compute n^2.

4.  Give a two-track Turing machine which, when initiated with two unary
    integers separated by a ";" on the first track, computes their product.

5.  Prove that recursively enumerable languages are closed under intersection.