6.045J/18.400J Handout 17: Problem Set 5– Due Friday, March 15

Marc Horowitz

Bronwyn Eliot, Thursday 1pm

Problem 1: Turing Machine Operation

If n is even, the machine will halt in the configuration (h, (#a)^{n/2+1}). If n is odd, the machine will never halt. It will hang in the configuration (q_{0}, #(#a)^{(n+1)/2}).

Problem 2: Designing a Turing Machine

q  σ_{1} σ_{2}  δ(q, σ_{1}, σ_{2})
q_{0}  # #  (q_{1}, L, #)
q_{1}  0 #  (q_{1}, L, #)
q_{1}  1 #  (q_{1}, L, #)
q_{1}  # #  (q_{2}, R, L)
q_{2}  0 0  (q_{2}, R, L)
q_{2}  1 1  (q_{2}, R, L)
q_{2}  0 1  (q_{3}, R, L)
q_{2}  1 0  (q_{3}, R, L)
q_{2}  # #  (q_{6}, L, #)
q_{3}  0 0  (q_{3}, R, L)
q_{3}  1 1  (q_{3}, R, L)
q_{3}  0 1  (q_{3}, R, L)
q_{3}  1 0  (q_{3}, R, L)
q_{3}  # #  (q_{4}, L, #)
q_{4}  0 #  (q_{4}, L, #)
q_{4}  1 #  (q_{4}, L, #)
q_{4}  # #  (q_{5}, N , N )
q_{5}  N N  (h, R, R)
q_{6}  0 #  (q_{6}, L, #)
q_{6}  1 #  (q_{6}, L, #)
q_{6}  # #  (q_{7}, Y , Y )
q_{7}  Y Y  (h, R, R)