知识/定理
图灵（1936）图灵机：形式化「可计算」概念；停机问题不可判定——计算机科学的奠基。
公式
停机问题：给定程序+输入，判其是否停机不可判定；$\text{HALT}$ 非递归集。
证明思路
（对角化）构造程序 $D$：若判停器说 $D$ 停则 $D$ 不停——归谬。
应用/例子
算法理论、编译器、人工智能、密码学。
意义/影响
可计算性理论的起点；图灵机成为「算法」的黄金标准，直接启发现代计算机。
DOXA · 数学编年史 · 知识详情
1936 ｜ 图灵 ｜ 逻辑 ｜ 突破
图灵（1936）图灵机：形式化「可计算」概念；停机问题不可判定——计算机科学的奠基。
停机问题：给定程序+输入，判其是否停机不可判定；$\text{HALT}$ 非递归集。
（对角化）构造程序 $D$：若判停器说 $D$ 停则 $D$ 不停——归谬。
算法理论、编译器、人工智能、密码学。
可计算性理论的起点；图灵机成为「算法」的黄金标准，直接启发现代计算机。