# Is a secondary TM sufficient to detect all loops?

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.

• 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). Oct 31, 2014 at 9:28
• @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?
– mafu
Oct 31, 2014 at 20:53
• (edited the question to clarify my intention)
– mafu
Oct 31, 2014 at 20:59
• 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. Oct 31, 2014 at 21:08