1. Use the schema of Lewis and Papadimitriou to construct:
   • a Turing machine that finds the middle of a string w in {a, b}*.

     That is, on input #w#, the machine halts in the configuration #xsy#
     where w = xsy, with s in {a, b}, x and y in {a, b}*
     |x| = |y| if |w| is odd and |x| = |sy| if |w| is even.

   • a Turing machine that decides the language {xx | x is in {a, b}*}.

     Assume that the input configuration is #w#.
     The halting configuration should be #Y# if w = xx, x in {ab} and #N# otherwise.

   • a Turing machine that performs integer division.

     On input configuration #<n ones>#<m ones>#, the machine halts in the configuration #<q ones># where q is the greatest integer less than n/m if m > 0 or 0 if m = 0.

2. Write up one to two pages on the Firing-Squad Problem. You may describe your own solution or a solution found, e.g. on the web. If you present someone else's solution, give references.

Last Updated: February 19, 2000 11:10 am by