什么是停机问题？
What is the halting problem?
停机问题问：能否写一个程序，判断任意给定程序在任意输入下是否会永远运行下去。图灵证明这是不可能的——不存在通用的停机判定器，说明有些问题计算机永远解不了。
The halting problem asks whether a program can decide, for any given program and input, whether it will run forever. Turing proved this impossible—no universal halting decider exists—showing some problems are forever beyond computation.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 来源待核验 · Source pending review
来源 · Source
出处备注：著录含书名，但缺版次 / 出版社 / 年份中的一部分，需编辑补全后才能做独立比对。
阿兰·图灵 1936 年论文《论可计算数》
Alan Turing, On Computable Numbers (1936)
#停机问题 #不可判定 #图灵
图灵机和丘奇-图灵论题是怎么定义『可计算』的？
How do the Turing machine and Church-Turing thesis define 'computable'?
图灵在 1936 年提出一种带读写头、在无限纸带上运作的抽象机器，能用精确规则模拟任何按部就班的算法；丘奇-图灵论题断言所有『直观可计算』的函数都能被图灵机计算。这成为现代计算理论的基石。
Turing proposed in 1936 an abstract machine with a read/write head on an infinite tape that can simulate any step-by-step algorithm by precise rules; the Church-Turing thesis asserts that every 'intuitively computable' function is computable by a Turing machine. It became the foundation of computation theory.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-11-05 · 4 条独立证据
来源 · Source
Turing《论可计算数》(1936)；Church《lambda 演算》(1936)；Sipser《计算理论导论》
Turing, 'On Computable Numbers' (1936); Church, 'An unsolvable problem' (1936); Sipser, 'Introduction to the Theory of Computation'
独立核验依据 · Independent verification: 核验依据 1 OPENLIBRARY 标识 /works/OL19859284W：Introduction to the th · 核验依据 3 Crossref DOI 10.2307/2371045
#图灵机 #丘奇-图灵 #可计算 #纸带
图灵机（Turing machine）是什么？它为什么是计算理论的基石？
What is a Turing machine, and why is it foundational to computation theory?
图灵机是图灵在 1936 年提出的抽象计算模型：一条无限长纸带加上一个按规则读写并移动的读写头，足以形式化『可计算』的概念。它定义了算法可解问题的边界，并引出了停机问题等不可判定性结论。几乎所有现代计算机的能力都不超出图灵机可模拟的范围。
A Turing machine, proposed by Turing in 1936, is an abstract model: an infinite tape plus a head that reads, writes, and moves according to rules, sufficient to formalize the notion of 'computable'. It defines the boundary of algorithmically solvable problems and yields undecidability results such as the halting problem. Essentially no modern computer exceeds what a Turing machine can simulate.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
Turing 1936；Sipser《计算理论导引》
Turing (1936); Sipser, Introduction to the Theory of Computation
独立核验依据 · Independent verification: 核验依据 1 OPENLIBRARY 标识 /works/OL19859284W：Introduction to the th
#图灵机 #可计算性 #停机问题 #图灵
为什么存在计算机『原则上也无法解决』的问题？
Why are there problems that are in principle unsolvable by computers?
图灵用对角线法证明『停机问题』不可判定：不存在一个通用程序能判断任意程序对任意输入是否会停机。还有忙碌海狸、希尔伯特第十问题等许多不可判定问题，说明算力再强也跨越不了某些边界。
Turing used a diagonal argument to prove the halting problem undecidable: no universal program can decide whether an arbitrary program halts on an arbitrary input. Many other problems—busy beaver, Hilbert's tenth—are likewise undecidable, showing even unlimited power has limits.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-11-03 · 2 条独立证据
来源 · Source
Turing《论可计算数》(1936)；Sipser《计算理论导论》
Turing, 'On Computable Numbers' (1936); Sipser, 'Introduction to the Theory of Computation'
独立核验依据 · Independent verification: 核验依据 1 OPENLIBRARY 标识 /works/OL19859284W：Introduction to the th · 核验依据 2 ISBN 9787111108405（豆瓣书目条目: 计算理论导论）；本条出处含多部著作，此标识只担保上面点名的
#停机问题 #不可判定 #图灵 #对角线
什么是丘奇-图灵论题？
What is the Church-Turing thesis?
丘奇-图灵论题猜想：凡是可有效计算的函数，都能被图灵机（或等价模型）计算。它不是可证明的定理，而是对计算本质的广泛共识，奠定了计算理论的根基。
The Church–Turing thesis conjectures that any function effectively computable can be computed by a Turing machine (or equivalent model). Not a provable theorem, it is a broad consensus on the nature of computation and underpins the theory.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
《计算理论导论》（Sipser）
Introduction to the Theory of Computation (Sipser)
独立核验依据 · Independent verification: 核验依据 1 ISBN 9787111108405（豆瓣书目条目: 计算理论导论）
#丘奇-图灵论题 #可计算性 #计算理论
有限自动机（finite automaton）和正则语言是什么关系？
What is the relationship between finite automata and regular languages?
正则语言是能用正则表达式描述的语言类，而有限自动机（确定型 DFA 或非确定型 NFA）正是识别这类语言的数学模型，二者在能力上完全等价。克林在 1956 年建立了正则表达式与有限自动机的对应关系，构成编译词法分析与文本匹配的理论基础。它处在乔姆斯基语言层级的最底层。
Regular languages are the class describable by regular expressions, and finite automata (deterministic DFA or nondeterministic NFA) are exactly the mathematical models that recognize them, with equivalent power. Kleene established the correspondence between regular expressions and finite automata in 1956, underpinning compiler lexical analysis and text matching. They sit at the base of the Chomsky hierarchy.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-11-03
来源 · Source
Kleene 1956；Sipser《计算理论导引》
Kleene (1956); Sipser, Introduction to the Theory of Computation
独立核验依据 · Independent verification: 核验依据 1 OPENLIBRARY 标识 /works/OL19859284W：Introduction to the th
#有限自动机 #正则语言 #克林 #乔姆斯基层级
什么是有限自动机？
What is a finite automaton?
有限自动机是一种只有有限个状态、按输入逐字符转移的计算模型，分为确定型（DFA）和非确定型（NFA）。它常用于词法分析和正则表达式的匹配。
A finite automaton is a model with finitely many states that transition on each input character, in deterministic (DFA) or nondeterministic (NFA) forms. It is widely used in lexical analysis and regular-expression matching.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
《计算理论导论》（Sipser）
Introduction to the Theory of Computation (Sipser)
独立核验依据 · Independent verification: 核验依据 1 ISBN 9787111108405（豆瓣书目条目: 计算理论导论）
#有限自动机 #状态 #正则表达式