Church-Turing论题

概述

Church-Turing论题是一个关于计算本质的经验性断言，声明任何直觉上可计算的函数都是图灵可计算的，或等价地说，所有合理的计算模型定义了同一个"可计算性"概念。

关键内容

1. 论题内容：
2. 任何直觉上"可计算"的函数都是图灵可计算的
3. 所有合理的计算模型（图灵机、λ演算、递归函数等）定义了同一个可计算性概念

4. 这不是一个数学定理，而是一个经验性的断言，无法被严格证明

5. 历史背景：

6. 由阿隆佐·丘奇和阿兰·图灵在1930年代独立提出
7. 图灵的图灵机模型与丘奇的λ演算被证明在可计算性上等价

8. 之后所有被提出的合理计算模型（递归函数、Post产生式系统、Markov算法等）都与图灵机等价

9. 重要意义：

10. 确立了"可计算性"概念的稳健性
11. 表明计算的本质是独立于具体形式化方式的客观概念

12. 为计算复杂度理论和算法理论提供了统一基础

13. 经验支持：

14. 自提出以来，从未发现反例
15. 所有合理的计算模型最终都被证明与图灵机等价

16. 包括现代的量子计算模型（在可计算性方面）

17. 强版本：

18. 标准版本只关注"可计算性"（是否可计算）
19. "强Church-Turing论题"关注"效率"（是否可高效计算），该版本可能被量子计算所挑战

来源

• 01-turing-on-computable-numbers — 图灵的相关工作
• 论可计算数及其在判定问题上的应用 — 附录中的等价性证明

相关

• 图灵机 — 主要模型之一
• λ演算 — 另一主要模型
• 阿兰·麦席森·图灵 — 提出者之一
• 丘奇 — 提出者之一
• 通用图灵机 — 理论重要支撑
• 可计算性理论 — 应用领域