Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

Problem 1

Consider the Turing Machine M:

Write down as a sequence of configurations the computation of machine M on input 011.

Problem 2

Here is the formal definition of the "yields in one step" relation for Turing machines:
For Turing Machine M = (Q,Σ,Γ,δ,s) configuration (q,u,x,v) yields (q',u',x',v') in one step if, letting δ(q,x) = (p,y,d):
(q',u',x',v') = {
(p,u,y,v) if d = S
(p,uy,v1,v2...vk) if d = R and v = v1v2...vk
(p,uy,  ,λ) if d = R and v = λ
(p,,um,yv) if d = L and u =, where m > 0
Oh yeah, q can't be h, the halt state!
This definition does not allow a TM to move the read/write head left from the first square on the tape.
  1. Circle the part(s) of the definition that describe the result of a "L" move.
  2. Explain what in that part of the definition disallows left moves from the first square of the tape.
  3. Show how to modify the definition so that left moves from the first square are allowed, but ignored; i.e. if you try to move left from the leftmost cell of the tape, you just stay in the same place.