| > The Halting Problem is famously only undecidable if the code you're analyzing is being modeled on a "Turing machine" or something equally "powerful" to it. The Halting Problem applies as long as you're able to programmatically combine two programs into a program that executes one with the other as its input. Given such a facility you can write a literal program whose input is a halting analyzer and whose output is a program on which the halting analyzer does not halt. Moreover the size of the output program seems to be something like twice the size of the analyzer plus the size of the program that combines pairs of programs as above. On computers with finite memory, this program (deriving from an analyzer a program on which the analyzer fails to halt) may itself not halt only if it runs out of memory. One conclusion is then a lower bound for the size of an analyzer as a fraction of available memory, and it seems the fraction would be close to a third. My personal opinion is this makes it practically impossible to make an analyzer. I think this because the size measure of the analyzer relative to memory is not in bytes but in terms of information content. What I mean is that size may refer to the size of a decompossion program plus a compressed archive of the would-be analyzer (this is an equivalent analyzer of smaller size). So the analyzer program would have compressed source code on the order of a third of available memory. Even worse, if we continue making computers with more memory, we would need bigger and bigger analyzers. Moreover, these cannot be procedurally generated by some algorithm that takes as input memory size, as this would violate the unbounded computation halting problem. So we would need bespoke large analyzer algorithms. Finally, just proving the correctness of such a code base that is not generated in some principled manner (as it would then be compressible) is also something practically impossible. In conclusion, such effort would be better spent on designing Turing-incomplete domain-specific languages with guaranteed behavior for which an analyzer is unnecessary. The latter is what people actually work with. In any case, below is the algorithm which takes as input a halting analyzer H and produces a program QQ on which the halting analyzer does not halt. It would perhaps be instructive to implement it and apply it to the cycle detection problem. --- Let H be some halting analyzer. By that I mean a program with the property that if HP, the program executing H with input P, halts with output 0, then executing P would not halt. Let N be a program that halts on input 0 and does not halt otherwise. Let N(HP) be the program that executes HP, and if the latter halts, executes N with input the result of executing HP. The behavior of N(HP) is that it halts if executing P would not halt in a way H could detect, and does not halt otherwise. Let Q be the program which takes input P and executes the program N(H(PP)). That is such that program QP, which executes Q on input P, halts if executing PP would not halt in way H can detect, and does not halt otherwise. Consider now the behavior of the program QQ, which excecutes Q with itself as input. It halts if executing QQ would not halt in a way H could detect, which is self-contradictory. So QQ most definitely does not halt. It follows that H(QQ) either does not halt or outputs 0. Outputting 0 is again self-contradictory, because that would mean executing N(H(QQ)) would halt, and by assumption QQ, which does not halt, is the program which executes N(H(QQ)). In conclusion, any halting analyzer H does not halt on input QQ, that is, the program which executes Q on itself as input, where Q is the program which takes input P, generates the program PP which would execute P on itself as input, and then executes N(H(PP)). |
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.