===========================================================================
CSC 363H                        Exercise 1                        Fall 2007
===========================================================================

 A. This exercise concerns TM M_2 whose description and state diagram
    appear in Example 3.7 (on p.143 of the textbook).  In each of the
    parts, give the sequence of configurations that M_2 enters when
    started on the indicated input string.

     a. 0
     c. 000

    (This is exercise 3.1 on p.159 of the textbook.)

 B. Write a formal-level description of a Turing machine that decides the
    language consisting of all strings of 0s whose length is a power of 2
    { 0^{2^n} : n >= 0 }, using the alternate convention mentionned in
    lecture (where the initial configuration has one blank square to the
    left of the input string).

 C. Give implementation-level descriptions of Turing machines that decide
    the following languages over the alphabet {0,1}:

     b. { w | w contains twice as many 0s as 1s }
     c. { w | w does not contain twice as many 0s as 1s }

    (This is exercise 3.8 on p.160 of the textbook -- a sample solution for
    part (a) appears on p.163.)