Why is the following language decidable? $L_{one\ right\ and\ never\ stops}$

Question

I can't understand how the following language can ever be decidable:

$L= \{ \langle M \rangle | M \ is \ a \ TM \ and\ there\ exists\ an\ input\ that\ in\ the\ computation\ $ $of\ M(w)\ the\ head\ only\ moves\ right\ and\ M\ never\ stops \}$,

but apparently it is.

We need to approve that there's at least one input as requested, so even if run on all inputs in parallel, we can't say something as "if it never stops, accept", it's paradox, and even if we could do that it was showing that the language is in $RE$- recursive enumerable.
so how come it is recursive?

Thanks a lot

Answer 1

As sdcvvc hints, this can be done due to how restricted the TMs in L are. The problem can be decided by examining the set of rules of the TM, which is finite. Firstly check if for some state $q_n$ the TM moves right on a blank input. This is the only way to go right infinitely as the tape contains only a finite number of symbols, other than a blank one. Secondly check that $q_n$ can be reached from $q_0$. For a normal TM this would not be decidable, but since this one can only go right, all of its input is the initial symbols of the tape.

Consider a graph representing this TM. The vertices are states and edges are symbols on which state changes. The direction is always right and the written symbol is irrelevant, so they do not need to be represented. This problem is equivalent to first finding a cycle that only uses blank symbol edges and then a path from starting vertex to this cycle in the graph.

Answer 2

I think that Karolis's answer is almost correct. I believe in order to deal with the possible non-determinism instead of constructing a graph whose vertices are the states of the TM $M$ in question, we should instead let the vertices be all nonempty sets of non-halting states.

Given any tape-symbol $\mathtt{a}$ we will draw a (directed) edge from vertex $A$ to vertex $B$ (labelled by $\mathtt{a}$) iff the following conditions are satisfied:

• for each state $q$ in $A$ the only instructions of $M$ with hypothesis $q,\mathtt{a}$ are of the form $q,\mathtt{a} \rightarrow q',\mathtt{b},R$ where $q'$ is a state in $B$ (in particular, no left moves are allowed, and no halting states can be entered);
• every state in $A$ has such an instruction (so every computation will continue at least one more step); and
• every state in $B$ is reachable from a state in $A$ by such an instruction.

We now analyse this directed, labelled graph.

• For each cycle in this graph consisting only of distinct blank-labelled edges we see if (some vertex in) this cycle is reachable from the vertex $\{ q_\text{start} \}$ using a path without cycles;
• If so, we accept $M$;
• If we run out of such blank-labelled cycles, we reject $M$.