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} (1) 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

Answer:

The class of language the machines recognise is Regular Language (See Explanation Below)

Explanation:

Given

Form δ : Q × Γ → Q × Γ × {R, S}

From the above transition form, it can be seen that the machine cannot read square symbols passed to it.

Regarding the square the machine is currently reading, there are multiple movement of S and it shouldn't be so because any number of the multiple movement can be simulated by exactly one movement of S.

As stated earlier that sequence of moves can be simulated by just one movement.

Let R = the movement

This means the machine can only use right move efficiently.

With this, we can say that the machine only read input string.

This is a characteristic of DFA (Deterministic Finite Automata).

With this, we can conclude that some DFAs will simulate the Turing machine and that they only read regular language.