数学中“可计算性”概念的建立

1. 可计算性问题的起源（20世纪初）
   可计算性概念源于希尔伯特在1900年提出的“判定问题”：是否存在一种通用算法，能判断任意数学命题的真假？这一问题的明确化需以“算法”的精确定义为前提。1930年代，哥德尔不完备定理表明数学形式系统存在不可判定命题，但未解决“算法有效性”的边界问题。图灵、丘奇等人在此背景下开始探索计算的本质极限。

2. 计算模型的提出与等价性（1936-1937）

   • 图灵机：图灵在1936年论文中抽象出“机械计算”的核心——一条无限长纸带、读写头和状态寄存器，通过简单规则（移动、改写符号）模拟任何计算过程。其关键创新是“通用图灵机”概念，可模拟其他图灵机的行为。
   • λ演算：丘奇独立提出λ演算，用函数抽象和应用构建计算系统，并证明其能表达所有可计算函数。
   • 等价性证明：图灵与丘奇分别证明图灵机、λ演算与递归函数（哥德尔-埃尔布朗定义）的计算能力等价，形成“丘奇-图灵论题”：直观可计算函数等价于形式模型可计算函数。

3. 不可判定性的具体发现
   图灵通过“停机问题”首次展现不可计算函数的存在：假设存在算法H可判断任意图灵机是否停机，可构造矛盾机器D，使D在H判定其停机时死循环，反之停机。这一自指悖论证明通用判定算法不可能，彻底否定希尔伯特判定问题的可行性。

4. 计算复杂性理论的萌芽
   1940-1950年代，可计算性研究自然延伸至“有效可计算性”。例如，时间/空间层次定理表明，更多资源能解决更多问题，但“P=NP?”等核心问题至今未解，成为理论计算机科学的基石。

5. 现代影响与跨学科扩展
   可计算性理论推动计算机科学（编译器设计、编程语言语义）、逻辑学（模型论、证明论）甚至物理学（量子计算对丘奇-图灵论题的扩展）的发展，其思想深度远超原始数学问题，成为理解信息处理本质的基础框架。