计算理论
概述
计算理论是计算机科学的理论基础，研究计算的本质、能力与限制，主要包含可计算性理论和计算复杂度理论两个分支。
关键内容
- 主要分支：
- 可计算性理论：研究哪些问题可以用算法解决，哪些不能
- 计算复杂度理论：研究可解问题的资源需求（时间、空间等）
-
自动机理论：研究抽象机器和计算模型
-
核心问题：
- 什么是计算？
- 什么是可以计算的？
- 什么是高效的计算？
-
计算有什么根本限制？
-
历史起源：
- 1930年代为解决希尔伯特的判定问题而诞生
- 丘奇的λ演算和图灵的图灵机为主要理论工具
-
奠定了整个计算机科学的理论基础
-
核心概念：
- 图灵机：通用计算模型
- Church-Turing论题：所有合理计算模型的等价性
- 停机问题：首个不可判定问题
-
P与NP：复杂度类的分类
-
理论意义：
- 证明了计算的根本边界
- 为算法设计提供理论指导
-
揭示了数学和逻辑的内在局限性
-
实际影响：
- 指导现代计算机设计
- 影响程序验证和安全性
- 为人工智能设定理论边界
来源
- 01-turing-on-computable-numbers — 计算理论的奠基之作
- 论可计算数及其在判定问题上的应用 — 创立性论文