论可计算数及其在判定问题上的应用

概述

阿兰·图灵于1936年发表的划时代论文，提出了图灵机概念，解决了希尔伯特判定问题，并奠定了计算机科学的理论基础。

关键内容

1. 论文基本信息：
2. 作者：Alan Mathison Turing
3. 发表时间：1936年5月28日提交，1937年正式出版
4. 期刊：伦敦数学学会会刊(Proceedings of the London Mathematical Society)

5. 领域：计算理论、数理逻辑

6. 核心贡献：

7. 图灵机模型：首次给出了"计算"的精确数学定义，通过抽象机器模拟人类计算员的行为
8. 通用图灵机：证明了存在一台能模拟任何其他图灵机的特殊机器，预言了可编程计算机的概念
9. 停机问题：证明了停机问题的不可判定性，揭示了计算的根本局限性

10. 判定问题的解答：否定回答了Hilbert的判定问题，证明不存在通用算法能判定一阶谓词逻辑中任意命题的真假

11. 历史意义：

12. 计算机科学的"创世文档"，为整个学科奠定了理论基础
13. 与Church的λ演算共同确立了Church-Turing论题
14. 证明了存在明确定义但不可算法解决的数学问题

来源

• 01-turing-on-computable-numbers — 详细分析与解读

相关

• 图灵机 — implements
• 通用图灵机 — implements
• 停机问题 — proves
• 判定问题 — application_to
• 希尔伯特纲领 — historical_context
• 阿兰·麦席森·图灵 — author