可计算性理论

概述

可计算性理论是研究哪些问题可以用算法解决的数学分支，也称递归论，是计算理论的两大分支之一（另一支为计算复杂度理论）。

关键内容

1. 核心问题：
2. 什么问题是可以用算法解决的？
3. 什么问题是不可能用算法解决的？

4. 如何形式化"算法"和"计算"的概念？

5. 主要模型：

6. 图灵机：阿兰·图灵提出的抽象计算模型
7. λ演算：阿隆佐·丘奇提出的函数抽象系统
8. 递归函数：哥德尔等人发展的数学函数类

9. Post系统：波斯特提出的符号变换系统

10. 等价性结果：

11. 上述所有合理的计算模型都被证明是等价的
12. 这为Church-Turing论题提供了经验支持

13. 所有模型定义了同一个"可计算性"概念

14. 关键结果：

15. 停机问题：第一个被证明不可判定的问题
16. Rice定理：图灵机的所有非平凡语义性质都不可判定

17. 判定问题：Hilbert提出的判定问题被证明无解

18. 与复杂度理论的区别：

19. 可计算性理论关注"是否可解"（是/否问题）

20. 复杂度理论关注"解的效率"（有多难解）

21. 历史发展：

22. 1930年代由丘奇、图灵、哥德尔等人创立
23. 为计算机科学奠定了理论基础
24. 证明了计算的根本边界

来源

• 01-turing-on-computable-numbers — 图灵机的原始定义
• 论可计算数及其在判定问题上的应用 — 创立性论文

相关

• 计算理论 — 上位概念
• 图灵机 — 主要模型
• λ演算 — 等价模型
• 停机问题 — 核心结果
• Church-Turing论题 — 理论基础
• 阿兰·麦席森·图灵 — 创立者
• 丘奇 — 创立者
• 哥德尔 — 理论贡献
• 计算复杂度理论 — 同级理论