On TM's with a single loop Thinking about the halting problem for TM's, I came up with a statement that I can't prove or disprove easily and would want your suggestions.
Conjecture: Given a TM whose digraph has a single cycle , and given that it loops forever on a word $w_1 \in \Sigma^*$. Then the set of words on which it loops forever is a regular language.
Question: Is this true or false , and how so?
Note that, if the TM's source code were written out in (say) C, it would have only a single loop  (for or  while ). Edit: The digraph consists of states for its nodes; if there is a transition $\delta(q_1, s) = (q_2, t, L/R)$, then there is a directed edge from $q_1$ to  $q_2$, marked with $s \rightarrow t, L/R$ in the digraph.    

It depends rather strongly on the exact definition of the digraph. If you really mean that there is only one cycle, then there are two cases:


*

*The net head movement is zero.

*The net head movement is non-zero.


In the first case, it is easy to see that the condition of entering an infinite loop depends on only a finite prefix of the input; in particular, the language is regular.
In the second case, we get the same result, though now we're using the fact that empty positions are different from input positions, and so the loop can only involve empty positions.
