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
    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).2011-04-10
  • 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
    By net head movement, do you mean net head movement in the loop? By "empty positions", do you mean blank tape cells?2011-04-10
  • 1
    Right on both counts.2011-04-10
  • 0
    Since both definitions led to the same conclusion, why say "it depends strongly on the exact defintion"?2011-04-10
  • 1
    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.2011-04-10
  • 1
    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.2011-04-10
  • 0
    Furthermore, the prefix argument only works if entering the loop in the state graph implies looping (= not terminating). That is not necessarily the case and might depend on the input. In particular, the loop might contain an accepting state, yielding a total machine.2011-04-10
  • 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
    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?2011-04-10
  • 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