Halting Problem

释义 / Definition

“停机问题”：计算理论中的经典问题——给定一个程序（或图灵机）和输入，判断该程序是否会在有限步内停止并输出结果，还是会无限运行。图灵证明：不存在一个对所有程序与输入都能正确判断的通用算法（该问题在一般情况下是不可判定的）。（在某些受限情形下可判定。）

发音 / Pronunciation

/ˈhɔːltɪŋ ˈprɑːbləm/

例句 / Examples

The halting problem shows that some questions cannot be solved by any algorithm.
停机问题表明，有些问题无法用任何算法彻底解决。

Researchers often reduce a new undecidable problem to the halting problem to prove it has no general solution.
研究者常把一个新的不可判定问题归约到停机问题上，以证明它不存在通用解法。

词源 / Etymology

“Halting”来自动词 halt（停止、终止运行），与“程序停止执行”这一含义直接相关；“problem”指数学或理论计算机科学中的“问题”。该术语因艾伦·图灵在1936年的工作而广为人知，成为“可计算性/不可判定性”研究的核心概念之一。

相关词 / Related Words

• Computability
• Decidability
• Undecidable
• Turing Machine
• Algorithm
• Reduction
• Rice's Theorem
• Church–Turing Thesis

文学与名著用例 / Notable Works

• Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem（1936）
• Douglas R. Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid（书中讨论可计算性与不可判定性时涉及停机问题）
• Michael Sipser, Introduction to the Theory of Computation（以停机问题作为不可判定性的核心例子）
• Martin Davis, Computability and Unsolvability（系统讨论停机问题与相关结果）
• Charles Petzold, The Annotated Turing（对图灵论文与停机问题的通俗注解）