| The Tortoise and Hare algorithm is a generic Halting analyzer which works for all finite-state machines, it always halts, it always correctly tells you whether the input program halts or not (as long you give it enough memory), and it is literally 18 lines of code. If the program P, which is the program being analyzed, uses at most N bytes of memory, then the Tortoise and Hare algorithm will always successfully determine whether P halts or not, if you give it 2*N bytes of memory. Specifically, if you run "QQ" with the Tortoise and Hare algorithm, you have 2 options: 1) If you give it a finite amount of memory (i.e. if you run it on a computer or some other kind of deterministic finite-state machine), then it will not do what you think it does. This is because the Tortoise and Hare algorithm, when applied to itself and having a finite memory limit, would exit unsuccessfully due to running out of memory, which would tell you nothing about whether it halts or not. 2) If you would analyze what it does on a Turing machine (i.e. an imaginary machine with infinite memory), then it would never halt, because it would always be trying to use more memory. I don't know if you realize this, but the underlying issue is that a Halting analyzer always needs to use more memory to analyze an input program than the amount of memory that the input program uses. Which means, of course, that when you apply the Halting analyzer to itself, it would need to use infinite memory in order to finish successfully, which is impossible. This is why the Halting problem is undecidable when programs are allowed to use infinite memory: because the Halting analyzer uses more memory than the input program. It is also why the Halting problem is decidable for finite-state machines. |