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