A Turing machine with stay put instead of left is similar to an ordinary Turing machine, but the transition function has the form
δ: Q×Γ→ Q×Γ×{R,S}
At each point, the machine can move its head right or let it stay in the same position. Show that this Turing machine variant is not equivalent to the usual version. What class of languages do these machines recognize?
It is easy to see that we can simulate any DFA on a Turing machine with stay put instead of left. The only non-trivial modification is to add transitions from the state in F to qaccept Upon reading a blank, and from states outside F to qreject Upon reading a blank.
Next, we start with a Turing machine M = (Q, Σ, Γ, δ, q0, qaccept, qreject) with stay put instead of left, and show how we can construct a DFA (Q', Σ' , δ', q' 0 , F) that recognizes the same language. The intuition here is that M cannot move left and cannot read anything it has written on the tape as soon as it moves right, and therefore it has essentially only one-way access to its input, much like a DFA
First, we modify M as follows; note that these changes do not affect the language it recognizes.
Set Q' = Q, Σ' = Σ, q '0 = q0, and consider the transition function:
(for q ∈ Q and σ ∈ Σ). Observe that there are finitely many state-alphabet pairs, M either ends up either staying put and looping, or eventually moves right, and thus δ 0 is well-defined. Finally, we define F to be the set containing qaccept and all states q ∈ Q, q ≠ qaccept, qreject such that M starting at q and reading blanks, eventually enters qaccept.
so these machines only recognize regular languages.
Get Answers For Free
Most questions answered within 1 hours.