L(M)=L where M is a TM that can move right or stay, so L is decidable

Question

Suppose that L(M)=L where M is a one tape TM that can move right or stay.

I need to Show that L is decidable.

I thought of reducing a PDA to this TM, since moving to the right is equivalent to popping and pushing some new symbol to the stack. and staying is the same as not touching the automata at all. but im not sure this is correct.

Answer 1

As dkaeae indicated in his comment, a right-moving or staying Turing machine (TM) is essentially a finite deterministic automaton (FDA). Here's a proof.

Let $M$ be such a machine, whose transition rules is in the form of $\delta(q, \gamma)=(t, \beta, d)$ where $q$ is the current state, $\gamma$ is the contents of the current cell, $t$ is the new state, $\beta$ is the symbol that replaces $\gamma$ in the current cell, and $d$ is the direction to move the head, which is either $R$ or $S$, meaning moving right or staying put respectively.

Let us check the behavior of $M$ when it has just applied a transition rule of the form $\delta(q, \gamma)=(t, \beta, S)$. Now $M$ is in state $t$ on top of $\beta$. In the next step, $M$ will read the symbol $\beta$, applying the unique rule on the pair $(t,\beta)$.

1. Suppose that rule is $\delta(t, \beta)=(u, \alpha, d)$.

   Then $M$ will change state to $u$, rewrite the current cell to $\alpha$ and move in the direction of $d$.

   We have found that once $M$ was in state $q$ on top of $\gamma$, it will change state to $u$, rewrite the current cell to $\alpha$ and move in the direction of $d$.

   So we can replace the transition rule $\delta(q, \gamma)=(p, \beta, S)$ by $\delta(q, \gamma)=(u, \alpha, d)$ in the specification of $M$ without changing the language accepted by $M$.

2. Suppose that rule is not defined.

   Then $M$ will halt. We can remove the transition rule $\delta(q, \gamma)=(p, \beta, S)$ in the specification of $M$ without changing the language accepted by $M$.

Applying the replacement or removal above repeatedly until there is no rule in $M$ that tells $M$ to stay in the same cell, we find that $L(M)$ is the language accepted by a right-moving only TM.

This question and answer tells us a right-moving only TM is essentially a DFA. Basically, a rule in a right-moving only TM, $\delta(q, \gamma)=(t, \beta, R)$ corresponds to $\delta(q, \gamma)=(t)$, a rule in the corresponding DFA. Since the language of a DFA is decidable, so is $L(M)$.

Answer 2

This inherently depends on your exact model of a TM, I'm assuming the following: A left-bounded tape, the head starts at position 0 and the word to decide is written at the tape. Furthermore, the TM has finitely many states.

Now the TM can only look at the first symbol at a time, can do finite computation (i.e. can have finitely many transitions to different states (*)) and move its head to the right once. Then it can repeat itself (**). In that, this TM is quit limited in what it can do, it can do as much as an DFA (like pointed out in the comments), that is: Look at a symbol, do some state-transitions and look at the next symbol.

(*) What happens, if the TM loops in the inner states without moving its head? Well, since there are only finitely many states, the Universal Turing Machine UTM can simulate the TM and just count how many transitions the TM has made since the last head movement to the right. If this number exceeds the number of states of the TM, the TM will not terminate, so the UTM can answer 'no'.

(**) What happens if the TM just goes to the right indefinitely? Well, at some point it will exceed the word to decide and move its head to a blank cell. An easy argument is to just count from there on the number of transitions (moving right or staying with the head at the current cell). If this number is greater than the number of states of the TM, it is caught in a loop and the UTM can answer 'no'.

To sum it up: The TM in question cannot decide its language, but the UTM can, so it is decidable in the usual sense.