Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Is $M$ taken as deterministic only? –  Arthur Fischer Aug 7 '12 at 10:38
1  
Hint: Since the head moves right only, it's not that different from a DFA. –  sdcvvc Aug 7 '12 at 10:46
    
@ArthurFischer: It can be deterministic or non-deterministic one. –  Jozef Aug 7 '12 at 10:53
    
@sdcvvc: Can you please extend your hint? –  Jozef Aug 7 '12 at 10:53
    
With the answer below this question might be moot, but I'll go ahead anyway: If $M$ is non-deterministic are you looking for an input $w$ such that for each computation of $w$ $M$ only moves to the right and never stops, or just for some computation? –  Arthur Fischer Aug 7 '12 at 11:45
show 3 more comments

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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$.
share|improve this answer
    
Would the answer to this question would change if the question was "for all input the head move right and never stop"? –  Jozef Aug 10 '12 at 14:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.