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.

  • $\begingroup$ How is the digraph defined? If it's a C program, note that every C program is equivalent to one with only a single loop (exercise). $\endgroup$ – Yuval Filmus Apr 10 '11 at 0:39
  • $\begingroup$ @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. $\endgroup$ – Ganesh Apr 10 '11 at 1:08

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.

| cite | improve this answer | |
  • $\begingroup$ By net head movement, do you mean net head movement in the loop? By "empty positions", do you mean blank tape cells? $\endgroup$ – Ganesh Apr 10 '11 at 1:29
  • 1
    $\begingroup$ Right on both counts. $\endgroup$ – Yuval Filmus Apr 10 '11 at 1:43
  • $\begingroup$ Since both definitions led to the same conclusion, why say "it depends strongly on the exact defintion"? $\endgroup$ – Ganesh Apr 10 '11 at 2:28
  • 1
    $\begingroup$ I only used one definition. Perhaps if you use a more lax definition, there are in fact more cycles, and things could get more complicated. $\endgroup$ – Yuval Filmus Apr 10 '11 at 5:40
  • 1
    $\begingroup$ ad case 1: Your phrasing is incomplete. You have a finite set of finite prefixes, therefore the language is regular. (in contrast to a prefix containing a loop: still finite prefixes, but potentially non-regular set). ad 2: why can the loop only move over empty positions? A very simple loop just hops between two neighbouring input symbols infinitely. Even a loop that just keeps going right (or left) might traverse over parts of the input before walking in the empty tape part. $\endgroup$ – Raphael Apr 10 '11 at 15:50

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.

| cite | improve this answer | |
  • $\begingroup$ TMs can read to the left, unlike DFAs. How are you handling this in your new DFA? Or does the nature of the single loop make it irrelevant? $\endgroup$ – Zach Langley Apr 10 '11 at 15:07
  • $\begingroup$ 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". $\endgroup$ – Raphael Apr 10 '11 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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