> 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)).