=====================================================================
                          Exercise 1                                 
=====================================================================
 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
   started on the indicated input string.

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

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

 2.  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
    b. 00
    c. 000
    d. 000000


   (This is exercise 3.1 on p.159 of the textbook.)
[in tutorial, we will start with a formal description of the machine,
then say it can be done with a diagram (and explain for the first
time); then show the runtime behaviour. at this point may or may not
use and explain configurations).

 3.  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. Can a Turing machine's head *ever* be in the same location in two
       successive steps?
    c. Can a Turing machine contain just a single state?