6
$\begingroup$

Procedure: Start a secondary TM in parallel with the first, but have the second perform exactly 1 step each 2 steps the first TM performs (i.e. it runs at half speed). If the second machine ever reaches the same configuration as the first, a loop was detected (obviously).

Claim: All infinite local loops in a TM can be detected in the above manner.

Local loop, in this context, refers to a machine running within a certain tape interval without ever stopping. To clarify, in particular this excludes any machines which extend the tape in any direction without bounds.

Has this been proven? I'm pretty sure I found this claim in a paper, I believe one of Marxen's, though I can't seem to find it.

Improve this question
$\endgroup$
  • $\begingroup$ Since you can simulate this pair of TMs with a normal TMs, this would mean the halting problem was co-semi-decidable and hence decidable (which it is not). $\endgroup$ – Raphael♦ Oct 31 '14 at 9:28
  • 1
    $\begingroup$ @Raphael I think I'm missing something. I thought the infinity produced by sideways runners would not be called 'loops' or 'cycles'. This means cycling infinite runners are restricted to a certain tape interval, in which they run indefinitely. This means they can always be detected, by simple state repetition, if their interval size is known. The question I had was why, in the pictured case, a secondary TM is already sufficient (instead of a keeping very long history). Or are you possibly rather saying that this meaningless anyway, because we cannot know the interval size? $\endgroup$ – mafu Oct 31 '14 at 20:53
  • $\begingroup$ (edited the question to clarify my intention) $\endgroup$ – mafu Oct 31 '14 at 20:59
  • 2
    $\begingroup$ This procedure will detect all infinite loops in which the Turing machine repeats a state, and no others. If you restrict your Turing machine's head to be within certain bounds, then it can only be in a finite number of states, and so if it never halts, it must repeat a state twice. $\endgroup$ – Yuval Filmus Oct 31 '14 at 21:08
7
$\begingroup$

This is Floyd's cycle finding algorithm, which is an efficient procedure for finding cycles. If you don't care about efficiency, you can use a big table which stores the different states the Turing machine has reached. If it reaches the same state twice, then it's in an infinite loop. What you are describing is just a more efficient way of detecting the same event, which is a particular type of infinite loop.

Turing machines can fail to halt – enter an infinite loop – in other ways. For example, a machine can keep going to the right indefinitely. The machine never halts, yet it doesn't reach the same state twice. A cycle finding algorithm won't detect this situation. Of course, there is no general way of detecting infinite loops, since the halting problem is undecidable.

Improve this answer
$\endgroup$

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.