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.