大型语言模型与停机问题：程序终止预测再探

Determining program termination is a fundamental problem in computer science. Turing's seminal work established the Halting Problem as undecidable, proving that no universal algorithm can determine termination for all programs and inputs. Consequently, automated verification tools approximate termination, sometimes failing to prove or disprove; these tools rely on problem-specific architectures and abstractions and are usually tightly coupled with particular technologies. The advent of Large Language Models (LLMs) and their remarkable performance in complex reasoning tasks offers a new perspective on program termination prediction. Although LLMs are inherently probabilistic models, lacking the deterministic computational capabilities of a Turing machine, their powerful pattern recognition and generalization abilities might provide useful heuristic predictions in specific scenarios. For instance, LLMs could learn patterns from vast amounts of program code and their execution traces, identifying common loop structures, recursive calls, and conditions that might lead to non-terminating behavior. Through semantic understanding of program code, LLMs might infer variable value ranges and function call depth limits, thereby assisting in determining whether a program will complete within a finite number of steps. However, LLM predictions are not rigorous mathematical proofs; they may exhibit limitations when confronting complex, non-linear program logic, especially with unseen program structures or adversarial inputs. Furthermore, the 'black-box' nature of LLMs poses challenges regarding the reliability and interpretability of their predictions. Integrating LLMs with traditional symbolic logic reasoning methods to form hybrid systems could potentially enhance trustworthiness while maintaining prediction accuracy.