Homework #8


1.  Design a Turing machine to recognize the language {ww^R:  w is in (0 v 1)*}.

    Solution:


                             X,X/R
        +--------------------------------------------------+
        |                                                  |
        |               0,0/R                   0,0/L      |
        |               1,1/R                   1,1/L      |
        |               +--+                    +--+       |
        |               |  |                    |  |       |
        |               v  | B,B/L              v  |       |
        +-->+--+ 0,X/R  +--+ X,X/L  +--+ 0,X/L  +--+       |
        --->|q1|------->|q2|------->|q3|------->|q4|-------+
        +-->+--+        +--+        +--+        +--+
        |   |  +----------------------+
        |   | 1,X/R                   | X,X/S
        |   v                         v
        |   +--+<--+ 0,0/R         +====+ 
  X,X/R |   |q5|   | 1,1/R         ||q8||
        |   +--+---+               +====+
        |   | B,B/L
        |   | X,X/L
        |   v
        |   +--+
        |   |q6|
        |   +--+
        |   |
        |   | 1,X/L
        |   v
        |   +--+<--+ 0,0/L
        +---|q7|   | 1,1/R
            +--+---+



2.  Show the sequence of configurations when processing the input
    001100 on the machine from problem 1.

    Solution:

      (q1, $_001100) |- (q2, $X_01100) |- (q2, $X0_1100)  |- (q2, $X01_100) |-
      (q2, $X011_00) |- (q2, $X0110_0) |- (q2, $X01100_B) |- (q3, $X0110_0) |-
      (q4, $X011_0X) |- (q4, $X01_10X) |- (q4, $X0_110X)  |- (q4, $X_0110X) |-
      (q4, $_X0110X) |- (q1, $X_0110X) |- (q2, $XX_110X)  |- (q2, $XX1_10X) |-
      (q2, $X011_0X) |- (q4, $X0110_X) |- (q3, $XX11_0X)  |- (q4, $XX1_1XX) |-
      (q4, $X0_11XX) |- (q4, $X_011XX) |- (q4, $X_X11XX)  |- (q1, $XX_11XX) |-
      (q5, $XXX_1XX) |- (q5, $XXX1_XX) |- (q6, $XXX_1XX)  |- (q7, $XX_XXXX) |-
      (q1, $XXX_XXX) |- (q8, $XXX_XXX)

3.  Design a Turing machine to compute n^2.

    Solution:

       The input to the machine is 0^n#.  To process a single 0 from the input,
       check it off (replace 0 with X), move past the remaining 0s and the
       #, and copy the entire input to the current location.  When all of the
       input is processed, change each 0 in the input to a blank and change
       the # to a blank.  Thus the resulting string will be B* 0^{n^2} B*.

4.  Give a two-track Turing machine which, when initiated with two unary
    integers separate by a ";" on the first track, computes their product.

    Solution:

    The Turing machine processes a single 0 from the first binary number in the
    following way.  The TM checks off a single 0 and then copies the entire
    second binary number to the second track.  The copy procedure is repeated
    for each 0 in the first binary number.  When all of the 0s in the first
    number have been checked off, all of the input on the first track is changed
    to blanks.  The resulting string on the second track will be the product of
    the two input binary numbers.

5.  Prove that recursively enumerable languages are closed under intersection. 

    Solution:

       If L1, L2 are recursively enumerable languages then there exist TMs
       M1, M2 that halt upon acceptance.  We can use M1 and M2 to construct
       a TM M that halts upon acceptance of a string in L1 ^ L2.


        +-------------------------------------------+
        |                                           |
        |      +--+ "yes"                           |
        |   +->|M1|------+                          |
        |  /   +--+       \                         |
        | /                ------>+---+             |
    w-----                        |AND|-------------------> "yes"
        | \                ------>+---+             |
        |  \   +--+ "yes" /                         |
        |   +->|M2|------+                          |
        |      +--+                                 |
        |                                           |
        +-------------------------------------------+