Cover Image

LLMs versus the Halting Problem: Characterizing Program Termination Reasoning

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Sultan, Oren, Armengol-Estape, Jordi, Kesseli, Pascal, Vanegue, Julien, Shahaf, Dafna, Adi, Yossi, O'Hearn, Peter
Format:	Preprint
Published:	2026
Subjects:	Computation and Language Artificial Intelligence Programming Languages
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Non-Termination Proving: 100 Million LoC and Beyond
by: Vanegue, Julien, et al.
Published: (2025)

ParallelPARC: A Scalable Pipeline for Generating Natural-Language Analogies
by: Sultan, Oren, et al.
Published: (2024)

Visual Editing with LLM-based Tool Chaining: An Efficient Distillation Approach for Real-Time Applications
by: Sultan, Oren, et al.
Published: (2024)

Logic.py: Bridging the Gap between LLMs and Constraint Solvers
by: Kesseli, Pascal, et al.
Published: (2025)

Agentic Separation Logic Specification Synthesis
by: Suresh, Tarun, et al.
Published: (2026)

SLaDe: A Portable Small Language Model Decompiler for Optimized Assembly
by: Armengol-Estapé, Jordi, et al.
Published: (2023)

One Joke to Rule them All? On the (Im)possibility of Generalizing Humor
by: Turgeman, Mor, et al.
Published: (2025)

Transformers are Multi-State RNNs
by: Oren, Matanel, et al.
Published: (2024)

Forklift: An Extensible Neural Lifter
by: Armengol-Estapé, Jordi, et al.
Published: (2024)

What I cannot execute, I do not understand: Training and Evaluating LLMs on Program Execution Traces
by: Armengol-Estapé, Jordi, et al.
Published: (2025)

Finding your MUSE: Mining Unexpected Solutions Engine
by: Sweed, Nir, et al.
Published: (2025)

Don't Overthink it. Preferring Shorter Thinking Chains for Improved LLM Reasoning
by: Hassid, Michael, et al.
Published: (2025)

State of What Art? A Call for Multi-Prompt LLM Evaluation
by: Mizrahi, Moran, et al.
Published: (2023)

LAST: Language Model Aware Speech Tokenization
by: Turetzky, Arnon, et al.
Published: (2024)

Cooking Up Creativity: Enhancing LLM Creativity through Structured Recombination
by: Mizrahi, Moran, et al.
Published: (2025)

Non-Halting Queries: Exploiting Fixed Points in LLMs
by: Hammouri, Ghaith, et al.
Published: (2024)

GmSLM : Generative Marmoset Spoken Language Modeling
by: Sternberg, Talia, et al.
Published: (2025)

Prompt Repetition Improves Non-Reasoning LLMs
by: Leviathan, Yaniv, et al.
Published: (2025)

Beyond Memorization: Distinguishing between Reductive and Epistemic Reasoning in LLMs using Classic Logic Puzzles
by: Gabay, Adi, et al.
Published: (2026)

Algorithmic Analysis of Termination Problems for Nondeterministic Quantum Programs
by: Fu, Jianling, et al.
Published: (2024)

Salmon: A Suite for Acoustic Language Model Evaluation
by: Maimon, Gallil, et al.
Published: (2024)

A Language Modeling Approach to Diacritic-Free Hebrew TTS
by: Roth, Amit, et al.
Published: (2024)

WHISTRESS: Enriching Transcriptions with Sentence Stress Detection
by: Yosha, Iddo, et al.
Published: (2025)

StressTest: Can YOUR Speech LM Handle the Stress?
by: Yosha, Iddo, et al.
Published: (2025)

InterFeat: A Pipeline for Finding Interesting Scientific Features
by: Ofer, Dan, et al.
Published: (2025)

Can LLMs Reason in the Wild with Programs?
by: Yang, Yuan, et al.
Published: (2024)

PAST: Phonetic-Acoustic Speech Tokenizer
by: Har-Tuv, Nadav, et al.
Published: (2025)

AutoCode: LLMs as Problem Setters for Competitive Programming
by: Zhou, Shang, et al.
Published: (2025)

Knowing What to Stress: A Discourse-Conditioned Text-to-Speech Benchmark
by: Turetzky, Arnon, et al.
Published: (2026)

Transformers for Program Termination
by: Alon, Yoav, et al.
Published: (2026)

Diffusion Language Models Generation Can Be Halted Early
by: Vaina, Sofia Maria Lo Cicero, et al.
Published: (2023)

Scaling Analysis of Interleaved Speech-Text Language Models
by: Maimon, Gallil, et al.
Published: (2025)

Unsupervised Speech Segmentation: A General Approach Using Speech Language Models
by: Elmakies, Avishai, et al.
Published: (2025)

Slamming: Training a Speech Language Model on One GPU in a Day
by: Maimon, Gallil, et al.
Published: (2025)

Demystifying Scientific Problem-Solving in LLMs by Probing Knowledge and Reasoning
by: Li, Alan, et al.
Published: (2025)

Mutual Reasoning Makes Smaller LLMs Stronger Problem-Solvers
by: Qi, Zhenting, et al.
Published: (2024)

Symbolic or Numerical? Understanding Physics Problem Solving in Reasoning LLMs
by: Dan, Nifu, et al.
Published: (2025)

On Code-Induced Reasoning in LLMs
by: Waheed, Abdul, et al.
Published: (2025)

SmolTulu: Higher Learning Rate to Batch Size Ratios Can Lead to Better Reasoning in SLMs
by: Alrashed, Sultan
Published: (2024)

Location Not Found: Exposing Implicit Local and Global Biases in Multilingual LLMs
by: Mor-Lan, Guy, et al.
Published: (2026)