LLMs versus the Halting Problem: Revisiting Program Termination Prediction

View PDF HTML (experimental)

Abstract: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. Recent success and progress in large language models (LLMs) raises the following question: can LLMs reliably predict program termination? In this work, we evaluate LLMs on a diverse set of programs from the Termination category of the International Competition on Software Verification (SV-Comp) 2025. Our results suggest that LLMs perform remarkably well at predicting program termination, where GPT-5 and Claude Sonnet-4.5 would rank just behind the top-ranked tool (using test-time-scaling), and Code World Model (CWM) would place just behind the second-ranked tool. While LLMs are effective at predicting program termination, they often fail to provide a valid witness as a proof. Moreover, LLMs performance drops as program length and complexity increases. We hope these insights motivate further research into program termination and the broader potential of LLMs for reasoning about undecidable problems.

Subjects:

Computation and Language (cs.CL); Artificial Intelligence (cs.AI); Programming Languages (cs.PL)

Cite as: arXiv:2601.18987 [cs.CL]

(or arXiv:2601.18987v4 [cs.CL] for this version)

https://doi.org/10.48550/arXiv.2601.18987

arXiv-issued DOI via DataCite

Submission history

From: Oren Sultan [view email] [v1] Mon, 26 Jan 2026 21:44:12 UTC (726 KB) [v2] Wed, 28 Jan 2026 13:02:15 UTC (726 KB) [v3] Thu, 29 Jan 2026 04:56:58 UTC (726 KB) [v4] Sat, 28 Mar 2026 10:34:08 UTC (765 KB)