Question

Question:A Turing machine with stay put instead of left is similar to an ordinary Turing machine, but the transition function has the form

$\mathbf{\delta }\mathbf{:}\mathbf{Q}\mathbf{\times }\mathbf{\Gamma }\mathbf{-}\mathbf{\to }\mathbf{Q}\mathbf{\times }\mathbf{\Gamma }\mathbf{\times }\left\{R,S\right\}\mathbf{.}$

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?

Short answer

Answer:

The statement is proved below.

Step-by-step solution

Step 1: Turing machine.

A Turing Machine is a mathematical model which consists of an infinite length tape divided into cells on which input is given. It consists of a head which reads the input tape. A state register stores the state of the Turing machine.

Language accept by the machine.

a).

A Turing machine with stay put instead of left is similar to an ordinary Turing machine, but the transition function has the form of,

$\mathbf{\delta }\mathbf{:}\mathbf{Q}\mathbf{\times }\mathbf{\Gamma }\mathbf{-}\mathbf{\to }\mathbf{Q}\mathbf{\times }\mathbf{\Gamma }\mathbf{\times }\mathbf{\{}\mathbf{R}\mathbf{,}\mathbf{S}\mathbf{\}}\mathbf{.}$

At each point, the machine can move its head right or let it stay in the same position.

Because head of TM can't move left, it will behave like a finite automata.

Motion of head in right is equivalent to consuming next symbol, and staying at a place is equivalent to consuming an epsilon symbol. When we hit blank symbol check if last state was accept state of TM, if yes then our finite automata accepts. Otherwise automata will reject the input string.
Not giving a formal definition of this TM and finite automata, because it is quite easy to visualization . Hence, the statement is proved.