LLMs versus the Halting Problem: Revisiting Program Termination Prediction

ArXi:2601.18987v4 Announce Type: replace-cross Determining whether a program terminates is a central problem in computer science. Turing's foundational result established the Halting Problem as undecidable, showing that no algorithm can universally determine termination for all programs and inputs. Consequently, automatic verification tools approximate termination, sometimes failing to prove or disprove; these tools rely on problem-specific architectures, and are usually tied to particular programming languages.