On the prompt formulation; prompts with very similar formulations (in terms of both semantics, hamming distance, or both) can lead to _wildly divergent_ outputs in my experience. It's not rigourous, and when that divergence happens, it's extremely difficult (arguably impossible, by nature of the architecture of transformers) to identify why the divergence happened and where.

It's not about being able to throw claude or codex at a loop and having it evaluate it for halting, it's about being able to do this for arbitrary code. Computer science rigourously defines the halting problem as not computable and undecidable. within the framework of using something akin to static analysis using any deterministic Turing machine.

There's not really a question of "solving" the halting problem like there's some as-yet unknown way of generally figuring out if arbitraty code halts. Turing proposed a proof in 1937 in favour of undecidability of what we now know as the halting problem, building on ideas first articulated by Church a few years prior.

Frankly, if anything, it's reasonable to say that the halting problem's been solved, just in the direction of undecidability rather than decidability.

Anyway, back to LLMs; as code gets more complex, the robot will need a bigger context window, more hardware resources, and more time, all of which will be variable due to the noise inherent in the system. It'll be difficult to put a useful upper and lower bound on how much computing power and time it'll take to figure out if a program ever halts. Which is all a bit moot, frankly, in the context of halting, but useful to keep in mind in the more general context of using these things as analysis tools.

IMO a better example would be the stochastic nature of quality control in manufacturing.