1
$\begingroup$

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.

  • 0
    @Yuval, I updated the definition. I suppose the solution to your exercise would be to wrap the program in a while loop,and remove all other loops, with appropriate break statements. I don't have more background.2011-04-10

2 Answers 2

2

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:

  1. The net head movement is zero.
  2. 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.

  • 0
    @Raphael: You're probably right. Do you care to work it out yourself and see what you get?2011-04-10
0

By "looping forever", I guess you mean that it does not leave the loop until the string ends. Since all inputs are finite, at some point the TM will stop at a certain state.

So, if you select the initial states before the loop and the loop, you have a DFA that recognizes the language, therefore it is regular.

You can make all the states that form the loop terminal. You can also modify the DFA so that the loop is completed at least once.

  • 0
    You can have a loop that does not consume a single input symbol, so the loop itself does not give you any information about the "looping language".2011-04-10