Question

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?

Answer 1

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 q_accept Upon reading a blank, and from states outside F to q_reject Upon reading a blank.

Next, we start with a Turing machine M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject) with stay put instead of left, and show how we can construct a DFA (Q', Σ' , δ', q' ₀ , 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.

• Add a new symbol so that M never writes blanks on the tape; instead, M writes the new symbol when it’s going to write blanks, and we extend the transition function so that upon reading this new symbol, it behaves as though it read a blank.

• When M transitions into q_reject or q_accept, the reading head moves right (and never stays put).

Set Q' = Q, Σ' = Σ, q '₀ = q₀, 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 q_accept and all states q ∈ Q, q ≠ q_accept, q_reject such that M starting at q and reading blanks, eventually enters q_accept.

so these machines only recognize regular languages.