Solution Found!
A Turing machine with stay put instead of left is similar
Chapter , Problem 3.13(choose chapter or problem)
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?
Questions & Answers
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:Step 1 of 3
Given data:
A Turing machine with stays put instead of left is similar to an ordinary Turing machine, but the transition function has the form:
.
At each point, the machine can move its head right or let it stay in the same position.