====================================================================
                          Exercise 1   (due Sep 24)                              
=====================================================================
 1.  This exercise concerns TM M_1 whose description and state diagram
   appear in Example 3.9 (on p.145 of the textbook).  In each of the
   parts, give the sequence of configurations that M_1 enters when
   startingn on the indicated input string.

    a. 11
    b. 1#1
    c. 1##1
    d. 10#11
    e. 10#10

 2.  Examine the formal definition of a Turing machine to answer the
   following questions and explain your reasoning.

    a. Can the tape alphabet T be the same as the input alphabet S?
    b. What are the possible locations of the Turing machine's head after three 
       steps of computation? Can you give an example of a single Turing machine 
       whose head will be at any of the options mentioned above, depending on the input?

 3. We say that a string in {0,1}* is "left dominated" if its lesmost bit is at least as big 
    as its rightmost bit, its second leftmost is at least as big as the 
    its rightmost bits, and so on - until the middle bits are compared. For example, the 
    following strings are left-dominated :
        10
        100
        10100101
        111
        100000
        1
        0
        empty-string

      while the folliwing are not :
        01
        001
        10101101

    Describe a Turing machine that decides the language L = {a in {0,1}* : a is left dominated}. 
    You should give a highlevel description, an implementation-level description and a formal description
    of your machine.