```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|------+                          |
|      +--+                                 |
|                                           |
+-------------------------------------------+
```