LLMs versus the Halting Problem: Characterizing Program Termination Reasoning

Oren Sultan, Jordi Armengol-Estape, Pascal Kesseli, Julien Vanegue, Dafna Shahaf, Yossi Adi, Peter O'Hearn

TL;DR

Frontier large language models (LLMs) like GPT-5 and Claude Sonnet-4.5 can predict program termination with an accuracy that rivals top-tier, specialized symbolic verification tools. However, a stark "classification-proof gap" remains: while these models excel at intuitively identifying whether a program will halt, they frequently fail to generate the formally verifiable graph-based proofs (witness automata) required by automated verifiers.

What Problem Does This Paper Address?

Program termination—determining whether a piece of code will eventually stop running or loop forever—is famously undecidable, a fundamental truth established by Alan Turing’s Halting Problem. Because no universal algorithm can solve it, the software verification community has spent decades building highly complex, language-specific symbolic tools to approximate termination analysis.

With the rapid rise of LLMs in coding tasks, the authors of this paper ask a natural question: To what extent can general-purpose frontier LLMs reason about program termination? If LLMs can successfully tackle this problem, they could offer a simpler, language-agnostic alternative or complement to traditional heavy-duty verification pipelines.

Methods

The authors evaluated several frontier models—including OpenAI's GPT-5, Claude Sonnet-4.5, Qwen3-32B, and CWM (a code world model)—alongside a non-reasoning baseline (GPT-4o).

To maximize the models' performance, they implemented a Test-Time Scaling (TTS) with Consensus Voting pipeline. Instead of relying on a single answer, the system generates multiple predictions and uses a strict consensus voting mechanism (requiring a unanimous vote among sampled outputs) to determine the final verdict. If the models disagree, it outputs "Unknown" to avoid the heavy scoring penalties associated with incorrect answers.

Furthermore, recognizing that the standard graph-based proof format used in formal verification is highly complex for text-based models, the authors introduced a novel divergence-precondition formulation. Instead of generating a state-transition graph, the LLM is asked to directly output a logical expression (e.g., x < 0 and y == 0) defining the exact input conditions that will cause the program to run indefinitely. These expressions are then mathematically validated using the Z3 theorem prover.

Datasets

The study utilizes two primary datasets:

  1. SV-COMP 2025 (Termination Category): The community-standard benchmark for software verification, containing 2,328 C programs spanning bit-precise arithmetic, complex control flows, and dynamic heap manipulation.
  2. Divergence Precondition Dataset: A newly introduced dataset created by the authors, consisting of 40 linear and 40 non-linear non-terminating programs from SV-COMP, manually annotated with ground-truth logical expressions that define their non-termination domains.

Key Insights and Ideas

  • The Classification-Proof Gap: LLMs possess strong semantic intuition; they can often correctly guess if a program terminates. However, they struggle with symbolic precision, frequently failing to construct the exact syntactical graph structure required to prove why it doesn't terminate.
  • Undecidable vs. Decidable Strengths: Interestingly, while LLMs often underperform classical solvers on decidable tasks like SAT solving (which require exhaustive, brute-force search), they are remarkably competitive on undecidable problems like termination. This suggests that undecidable problems, which rely heavily on heuristic reasoning and pattern recognition, are a more natural fit for LLM capabilities.
  • Format Matters for Proofs: Shifting the proof requirement from a complex graph-based automaton to a logical precondition formula significantly boosted model accuracy, showing that traditional verification formats may be an artificial bottleneck for language models.

Key Results

When boosted by Test-Time Scaling, frontier LLMs achieved performance levels that directly challenge state-of-the-art symbolic verifiers.

Figure 3: SV-COMP main results. Mean SV-COMP scores for LLMs (across 100 bootstraps), top SV-COMP 2025 verification tools, and the max possible scores (minimum score is −50,064). GPT-5 (TTS) and Claude Sonnet-4.5 (TTS) would place 2nd and 3rd (3,520 and 3,448), behind the gold medalist PROTON. CWM ranks just below UAutomizer. GPT-4o scores significantly lower: 546 with TTS, and a negative score without TTS (−5, 145).
  • Top-Tier Performance: GPT-5 achieved an SV-COMP score of 3,520 and Claude Sonnet-4.5 scored 3,448, effectively placing them 2nd and 3rd in the global competition rankings, trailing only the specialized tool PROTON (3,685) and outperforming the runner-up UAutomizer (3,334).
  • Open-Weights Success: CWM scored 3,129, performing competitively just below UAutomizer.
  • The Length Bottleneck: Across all models, performance degraded significantly as the complexity and length of the code increased, highlighting a vulnerability in long-context global reasoning.
Figure 4: LLMs mean SV-COMP score vs. code length. Dataset examples are grouped into three equal size bins by code length (measured in tokens using In- struct Llama3 Tokenizer) (x axis). The mean SV-COMP score (y axis) per bin is shown for all models (20 pre- dictions per sample). Scores decrease with code length; GPT-5 leads, followed by Claude and CWM.
  • Precondition Accuracy: On the newly proposed domain witness task, Claude Sonnet-4.5 achieved an impressive 87% Pass@1 accuracy on linear conditions and 77% Pass@1 on complex, non-linear polynomial conditions.

Limitations and Future Work

  • Language Scope: The evaluation was strictly limited to C programs within the SV-COMP benchmark.
  • Opaque Architectures: The highest-performing model, GPT-5, is proprietary, meaning its internal reasoning tokens and exact scale remain unknown.
  • Prompt Sensitivity: Like most LLM tasks, performance can fluctuate based on minor prompt adjustments, though the authors mitigated this by using a simple, unoptimized standardized prompt.
  • Future Directions: The authors advocate for neuro-symbolic approaches—combining the intuitive, language-agnostic reasoning of LLMs with the rigorous, absolute correctness of symbolic proof checkers—and expanding benchmarks to evaluate real-world, repository-level codebases.

Summary updated

Abstract

Determining whether a program terminates is a central problem in computer science. Turing's Halting Problem established termination as undecidable, showing that no algorithm can universally determine termination for all programs and inputs. Hence, 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. Recent advances in LLMs raise a natural question: To what extent can they reason about program termination? We evaluate frontier LLMs on a diverse set of C programs from the International Competition on Software Verification (SV-Comp) 2025. Our results show that GPT-5 and Claude Sonnet-4.5 achieve scores comparable to top-ranked verification tools (with test-time scaling). However, while models often correctly infer whether programs terminate, they frequently fail to construct a witness as formal proof, revealing a gap between semantic recognition and symbolic proof generation. Performance further degrades as code length increases. Beyond witness automaton graphs, we introduce a divergence-precondition formulation that characterizes non-termination conditions as logical constraints. We hope these findings motivate future research on real-world termination benchmarks, neuro-symbolic approaches that combine LLMs with symbolic verification methods, and, more broadly, LLM reasoning on other undecidable problems.
BibTeX
@misc{sultan2026llms,
  author = {Oren Sultan and Jordi Armengol-Estape and Pascal Kesseli and Julien Vanegue and Dafna Shahaf and Yossi Adi and Peter O'Hearn},
  title = {{LLMs versus the Halting Problem: Characterizing Program Termination Reasoning}},
  year = {2026},
  eprint = {2601.18987},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2601.18987},
}
Figure