可计算性理论 可计算性理论是研究“计算”这一概念的数学理论，它的核心问题是： 什么样的函数可以被算法计算？ 我们将从直观的“计算”概念出发，逐步引入形式化的计算模型和关键定理。 1. 计算的直观概念与希尔伯特计划 在20世纪初，数学家试图为数学建立严格的基础。希尔伯特提出一个计划：希望找到一套完备且一致的公理系统，使得所有数学命题均可通过机械步骤（算法）判定真伪。但这一计划需要先明确“机械步骤”的定义。 2. 形式化计算模型的提出 为了精确描述“算法”，数学家提出了多种计算模型，它们后来被证明是等价的（即计算能力相同）： 图灵机 ：通过一条无限长的纸带、读写头和状态转移规则模拟计算过程。 λ演算 ：通过函数抽象和应用规则定义计算（你已学过，此处不展开）。 递归函数 ：从基本函数（如常数函数、投影函数）出发，通过复合、原始递归和极小化操作构造复杂函数。 3. 可计算函数的定义 若存在一个算法（如图灵机程序），对任意输入能在有限步内输出结果，则称该函数是 可计算的 。例如，加法、乘法是可计算函数，而“判断一个程序是否停机”的函数则不是（见下文）。 4. 停机问题与不可判定性 图灵在1936年证明了 停机问题 的不可判定性： 问题：能否设计一个程序 \( H(P, x) \)，判断程序 \( P \) 在输入 \( x \) 下是否会停机？ 证明：假设 \( H \) 存在，可构造一个程序 \( D \)：若 \( H(D, D) \) 输出“停机”，则 \( D \) 进入死循环；否则 \( D \) 立即停机。这导致矛盾，故 \( H \) 不存在。 这一结论表明， 存在明确定义但不可计算的问题 ，从而否定了希尔伯特计划中“完全机械化判定”的可能性。 5. 丘奇-图灵论题 所有合理的计算模型均等价于图灵机，这一经验性结论称为 丘奇-图灵论题 。它并非数学定理，而是可计算性的标准定义，至今未被推翻。 6. 可计算性理论的扩展 相对计算 ：引入“预言机”概念，研究在特定问题已解决的前提下可计算性的变化（如图灵度）。 计算复杂性理论 ：在可计算的基础上，进一步研究计算所需的时间、空间资源（如P与NP问题）。 通过以上步骤，我们看到了可计算性理论如何从直观计算概念深化为形式化模型，并揭示计算的本质界限。这一理论是计算机科学的基石，直接影响编程语言设计、算法分析和人工智能的可行性研究。