1 定义与基本概念
1.1 计算与算法的直观理解
计算通常被理解为通过明确、有限的规则对符号进行机械式变换的过程。算法的直观含义是一组精确的、无歧义的指令序列，只要机械地执行这些指令，就能在有限步骤内从输入得到输出。例如，小学算术中的竖式加法、解一元二次方程的求根公式，都是算法的典型实例。一个计算（或算法）的有效性依赖于其操作的确定性：每一步必须清晰可执行，不存在“猜测”或“无限循环”这样的模糊性。然而，并非所有看起来“有规律”的数学问题都能被这样的有限机械过程所求解：可计算性理论正是为了区分“哪些问题有算法”与“哪些问题没有算法”而诞生的。
1.2 可计算函数与可判定问题
1.2.1 部分函数与全函数
在可计算性理论中，函数被分为两类：全函数和部分函数。全函数对所有可能的输入都有定义，即对于定义域中的每一个元素，函数都返回一个确定的输出。部分函数则允许在某些输入上没有定义——这意味着对于这些输入，对应的计算过程可能永远不会终止（例如陷入无限循环）。将部分函数纳入讨论是必要的，因为许多自然定义的算法（如寻找满足某性质的整数、模拟图灵机运行）对某些输入可能永远停不下来。一个函数被称为“可计算”即指存在一个算法，对于其定义域内的输入给出正确结果，而对于定义域外的输入该算法可能永远不终止。
1.2.2 判定问题与半判定问题
1.2.2.1 可判定性
一个判定问题指的是答案为“是”或“否”的问题，通常表示为语言识别：给定一个字符串（或自然数的编码），判断它是否属于某个集合/语言。若存在一个算法，对每一个输入都能在有限时间内给出正确的“是/否”回答，则称该问题是可判定的（或递归的）。例如，“给定一个整数，判断它是否为偶数”是一个可判定问题，因为可以快速写出一个确定性算法。可判定性问题意味着算法的运行总是终止，且输出唯一确定。
1.2.2.2 半可判定性
如果一个判定问题只要求对答案为“是”的输入能在有限时间内确认（即输出“是”并终止），而对于答案为“否”的输入可能永远不终止或无法确定，则该问题是半可判定的（或称递归可枚举的）。更正式地，一个语言L是半可判定的，当且仅当存在一个算法，当输入属于L时总能停机并接受，当输入不属于L时要么停机拒绝要么永不停机。半可判定性是许多不可判定问题的自然特征：例如，尽管停机问题不可判定，但它本身是半可判定的——因为可以模拟目标程序的运行，如果它停机就输出“是”，但若它不停机则模拟者永远在运行。
1.3 有效枚举与枚举可计算性
有效枚举也叫递归枚举，是指存在一个算法能够逐一列出某个集合的所有成员（允许重复，且顺序无关紧要）。若一个集合是递归可枚举的（半可判定的），它就可以被有效枚举：算法只需穷尽所有可能的输入，并测试每个输入是否属于集合，当发现属于时便输出该元素。反过来，若某个集合可以被有效枚举，那么它一定是半可判定的：要判断一个元素x是否属于集合，只需检查枚举过程是否会在有限步骤内输出x。有效枚举为理解半可判定性提供了直观：集合的元素可以被一个不知疲倦的机器逐个打印出来，但无法保证所有“非成员”被排除。
2 计算模型的形式化
2.1 图灵机模型
2.1.1 基本结构（带子、状态、转移函数）
图灵机由以下部分组成：
- 无限长的带子：被划分为大小相等的格子，每个格子可容纳一个符号（来自有限字母表）。带子初始时包含输入字符串，其余格子为空白符号。
- 读写头：可以读取当前格子的符号，并改写该格子，然后向左或向右移动一格。
- 有限状态机：包含有限个状态，其中包括一个初始状态和若干个接受/拒绝状态。
- 转移函数：规则形如“当前状态q、当前符号a → 新状态p、新符号b、移动方向（L/R）”。转移函数决定了图灵机的动作，它是确定性的（每一步由当前状态和符号唯一确定）。
图灵机的运行是离散时间步：每一步根据当前状态和读写头下的符号，执行相应的状态改变、符号改写和头部移动。若在某个时刻进入接受或拒绝状态则停机，否则可能永远运行下去。有限条转移规则决定了无限长的计算过程。
2.1.2 图灵机可计算函数
一个函数f: Σ* → Σ* 被称为图灵机可计算，如果存在一台图灵机，当输入字符串w时，它最终停机，且停机时带子上的内容恰好是f(w)（通常约定所有非空白符号表示输出）。对于部分函数，若图灵机在某个输入上不停机，则认为该输入不在函数的定义域内。由于图灵机可以执行任意的符号操纵、循环、条件分支，其计算能力被公认为代表了“有效算法”的极限。
2.1.3 通用图灵机与可计算性等价性
通用图灵机是一种特殊的图灵机，它可以读取其他图灵机的描述（编码）及其输入，然后模拟目标图灵机的行为。这一构造表明：一台固定的机器可以执行任意算法，只需将算法作为数据输入。通用图灵机的存在意味着“可计算”是一个统一的概念：如果一个函数能够被某台图灵机计算，它就能被通用图灵机模拟。不同计算模型（如λ-演算、递归函数、波斯特系统）之间的相互模拟证明了它们定义的是同一个函数集合——这就是“可计算的精确边界”。
2.2 递归函数（μ-递归函数）
2.2.1 初始函数与复合、递归、极小化操作
递归函数通过一组基础构件和运算来定义。初始函数包括：
- 零函数：Z(x) = 0
- 后继函数：S(x) = x+1
- 投影函数：U_i^n(x1,...,xn) = xi
从初始函数出发，通过以下运算法则构造新函数：
- 复合：把已知函数的输出作为另一个函数的输入。
- 原始递归：定义一个函数，其值通过递归在自然数上逐步计算，例如f(0)=常数，f(n+1)=g(n,f(n))。
- 极小化（μ算子）：对于给定的函数g，定义f(x) = 最小的y，使得g(x,y)=0，且对所有小于y的z，g(x,z)均有定义。若不存在这样的y，则f(x)无定义。
极小化算子是关键，因为它允许定义部分函数（当不存在最小y时函数无定义）。所有由初始函数经过有限次复合、原始递归和（允许部分定义的）极小化而得到的函数称为部分递归函数。
2.2.2 原始递归函数与部分递归函数
原始递归函数是那些仅通过复合和原始递归（不使用极小化算子）构造的函数。所有原始递归函数都是全函数（对所有自然数都有定义），而且它们包括了常见的加法、乘法、幂运算、斐波那契数列等。然而，原始递归函数不足以涵盖所有可计算函数：存在一个可计算的全函数不是原始递归的，例如阿克曼函数。部分递归函数则通过引入μ算子允许捕获所有可计算函数——包括那些只有部分定义域的函数（例如“寻找约数的个数”中的无限循环情形）。丘奇-图灵论点断言：部分递归函数恰是直觉上可计算的函数。
2.2.3 递归函数与图灵机的等价性
可以证明，图灵机可计算函数类恰好等于部分递归函数类。证明分两个方向：一方面，模拟图灵机的每一步可以编码为自然数上的原始递归运算，其停机条件对应μ算子；另一方面，递归函数的计算过程可以通过图灵机构造。这一等价性有力地支持了丘奇-图灵论点：直觉的“可计算”就是这两种形式化模型所表示的函数集合。
2.3 λ-演算
2.3.1 λ-项与归约规则
λ-演算由阿隆佐·丘奇提出，是一种基于函数定义与应用的纯形式系统。λ-项由以下规则递归定义：
- 变量：x, y, z, ...
- 抽象：λx.M（表示以x为参数、以M为体部的函数）
- 应用：M N（将函数M应用到参数N）
主要归约规则是β-归约：((λx.M) N) → M[x:=N]（将N替换到M中所有自由出现的x处）。例如，(λx.x+1) 5 → 5+1 → 6（假设+和数字已被编码）。λ-演算中的计算就是反复应用β-归约直至无法归约（范式），或无限归约（无定义）。条件判断和递归（通过不动点组合子如Y组合子）可以在纯无类型的λ-演算中编码，使其具有通用计算能力。
2.3.2 丘奇-图灵论点
丘奇-图灵论点并非一个可证明的定理，而是一个关于“可计算”概念的假设：一个函数被直觉认为可以通过有效算法计算，当且仅当它可以用图灵机（或等效的λ-演算、递归函数）计算。几乎所有已知的计算模型都被证明彼此等价，且无一模型能超出这个范围，因此该论点被广泛接受。不过，论点本身是开放性的：如果有朝一日发现一种现象上有效却无法被图灵机模拟的计算过程（例如某些量子或超计算假设），则论点需要修订。
2.4 其他等价模型
2.4.1 波斯特对应系统
波斯特系统是一种基于字符串重写的计算模型：它由一组有限规则集（类似于“从左边模式替换为右边模式”）构成，系统从初始字符串开始，反复应用规则进行替换。通过适当编码，波斯特系统可以模拟图灵机，反之亦然，因此它与图灵机等价。波斯特对应问题（Post Correspondence Problem）在其基础上衍生为典型的不可判定问题。
2.4.2 马尔可夫算法
马尔可夫算法使用一组有序的字符串替换规则（每条规则指定一个字符串模式和一个替换结果），执行时总是选择当前字符串中能匹配的最左边规则进行替换，直到没有可应用的规则为止。马尔可夫算法被发现与图灵机计算能力相同，且常被用来形式化地定义算法规范。
2.4.3 寄存器机
寄存器机（亦称计数机）具有有限数量的寄存器，每个寄存器可存储任意大的自然数，程序由有限条指令组成（如增1、减1（若为0则跳转）、无条件跳转）。寄存器机虽然结构简单（没有无限带子），但同样可以模拟图灵机，因此也是通用计算模型。它的简洁使得它常被用作计算理论教学中的过渡模型，并可方便地证明某些问题的不可判定性。
3 不可计算问题
3.1 停机问题
3.1.1 停机问题的定义与证明（自指与对角线法）
停机问题是：给定一个程序P（或图灵机的编码）和输入w，判定P在输入w上是否最终停机。阿兰·图灵在1936年证明了这个问题不可判定。
证明采用反证法并依赖于自指和对角线法： 假设存在一个图灵机H，它以程序P（转换为编码）和输入w为输入，输出“停机”或“不停机”。构造一个新图灵机D：它接受一个程序编码x，模拟H(x, x)，若H输出“停机”则让D进入无限循环；若H输出“不停机”则让D直接停机。现在运行D(D)：
- 若H(D, D)输出“停机”，则D应进入无限循环——矛盾。
- 若H(D, D)输出“不停机”，则D应直接停机——也矛盾。
因此，H不可能存在，停机问题不可判定。
3.1.2 停机问题的不可判定性推论
停机问题的不可判定性带来许多推论：
- 不存在通用的程序调试器，能判断任意程序是否会在给定输入上死循环。
- 许多关于程序行为的性质（如两程序是否等价、是否能输出特定值、是否会在某输入上访问特定内存）皆不可判定。
- 停机问题自身的不可判定性意味着“解决所有可计算问题的全能算法”不存在，从而宣告了希尔伯特“判定问题”的否定答案。
3.2 其他典型不可判定问题
3.2.1 波斯特对应问题
波斯特对应问题（PCP）是：给定两组词（字符串）列表，每组包含数量相同的词（如A1,...,An和B1,...,Bn），问是否存在一个非空索引序列i1,i2,...,ik，使得由A组词按顺序拼接的结果等于由B组词按顺序拼接的结果。虽然该问题描述很简单，但可以证明它是不可判定的：通过将图灵机的计算过程编码为词的拼接问题，可以把停机问题归约到PCP。因此不存在通用算法求解所有PCP实例。
3.2.2 希尔伯特第十问题（丢番图方程可解性）
希尔伯特第十问题询问：是否存在一个通用算法，给定一个整系数多元多项式方程（即丢番图方程），判定它是否有整数解。马季亚谢维奇在1970年证实了该问题不可判定。证明利用了递归可枚举集的算术刻画：能够证明每个半可判定的集合都可以表示为一个丢番图方程的解集。由于存在不可判定（即非递归）的半可判定集，所以丢番图方程的可解性判定本身不可判定。例如，方程x² + y² = z²容易判定（验证勾股数），但更复杂的方程如“a³ + b³ = c³”再加一些条件可能无法通用地解决。
3.2.3 群论中的字问题
群论中的字问题（Word Problem）：给定一个有限表示的群（由生成元和关系定义），以及两个由生成元构成的词，判定它们在群中是否表示同一个元素。诺维科夫与布恩分别在1950年代独立证明了存在有限表示的群其字问题不可判定。这个结果说明，尽管群是简单的代数结构，但关于其元素等价性的判定可以复杂到算法不能解决的程度。它激励了组合群论、可计算群论的研究。
3.3 可归约性与不可计算度
3.3.1 许多一归约与Turing归约
为了比较不同不可判定问题的“难度”，引入归约的概念。许多一归约是说：问题A许多一归约到问题B（记为A ≤m B），如果存在一个可计算的函数f，使得对于任意输入x，x属于A当且仅当f(x)属于B。若B是可判定的，则A也可判定；反之，若A不可判定，则B也不可判定。
更强大的图灵归约考虑用一个关于B的“预言机”来解决问题A：在计算过程中可随时查询B的答案（预言机可在常数时间内给出正确回答），且允许多次查询。图灵归约更灵活，它将许多一归约作为特例。如果A图灵归约到B且B图灵归约到A，则称A和B是图灵等价的。
3.3.2 图灵度与跳变算子
所有相互图灵等价的问题形成等价类，称为图灵度。图灵度之间有一个自然的偏序：如果一个度中的问题可以归约到另一度中的问题，则前者≤后者。最低的度是所有可判定问题（递归集）构成的度（常常记作0）。比0高的度包括停机问题的度（记作0'），它代表了最自然的非递归可计算度。跳变算子是一种提高度的操作：将给定度中的某个问题（一般是某种“极限”表述）的形式化对象（比如“此图灵机停机”的预言）编码为一个新的集合，其度严格大于原有度。反复应用跳变可以得到无穷阶的度层次，例如0, 0', 0'', ... 每一层都比前一层更“不可判定”。
4 计算复杂度理论的联系
4.1 时间与空间复杂性初步
可计算性讨论“是否可计算”，而计算复杂性讨论“需要多少资源（时间、空间）”。给定一个可计算的判定问题，自然关心是否存在一个算法能在多项式时间内解决它，或只消耗对数空间。经典复杂度类（如P、NP、PSPACE、EXPTIME）都是在可计算性的基础上进一步划分。可计算性保证了算法存在（可能指数或更高复杂度），而复杂性理论则试图寻找这些算法的效率边界。
4.2 可计算性与可判定性的边界
4.2.1 递归可枚举集与非递归集
递归可枚举集（RE）是那些半可判定（即为某个图灵机的接受语言）的集合。非递归集是指那些既是递归可枚举但又非递归的集合：它们半可判定但不可判定——例如停机问题的集合。非递归集的存在意味着可判定集（递归集）与半可判定集之间的严格包含关系。实际上，递归可枚举集中包含了所有可判定集，但还存在大量既非递归又非RE的集合（如补非RE的集合）。这些集合不在任何一个递归可枚举的层次中。
4.2.2 算术层级
算术层级（Arithmetic Hierarchy）将自然数上的公式（带量词）按照量词交替的复杂度进行分层。每个层次（Σ_n或Π_n）对应一类定义集：Σ₁集恰是递归可枚举集；Π₁集是Σ₁集的补集（余递归可枚举）；Σ₂集是那些可以用“存在x对所有y都成立”形式的公式定义的，等等。在递归可枚举集以上的更高层次中，集合的不可判定性更加“复杂”。该层级将可计算性理论中的度（如跳变）与逻辑公式的复杂性联系起来，揭示了不可判定性的程度可以用量词数量来刻画。
4.3 从可计算性到计算复杂性
4.3.1 时间层次定理的非构造性
时间层次定理指出：对于某些时间资源，增加适当多的时间（例如从n^k到n^(k+1)）能够计算新的语言，即存在一些语言可以被O(n^(k+1))时间的算法计算，却不能由O(n^k)时间的算法计算。但这些定理的证明通常是非构造性的：它们通过对角化方法（类似于停机问题的证明）构造出这样的语言，并不提供一个实际的“有用”问题。可计算性理论中的对角化技巧直接启发了复杂性理论中的空间层次及时间层次结果。
4.3.2 NP完全问题与可计算性无关性
NP完全问题是“NP中最难的问题”，而NP是类可判定但可能指数时间。值得注意的是，NP完全问题的不可解性（即P≠NP是否成立）是一个与可计算性无关的问题：所有的NP问题都是可判定的（因为非确定性图灵机可以在有限时间内停机给出答案）。可计算性理论不关心问题的效率，只关心是否可算法求解。因此，P=NP的猜想完全属于计算复杂性的范畴，不涉及可计算性边界。停机问题等不可判定问题是不可计算的，而NP完全问题始终是可计算的，只是效率疑问。
5 历史与哲学意义
5.1 关键人物与里程碑
5.1.1 哥德尔不完全性定理的奠基
在可计算性理论诞生之前，哥德尔1931年证明了不完全性定理：任何足够强大的公理系统（如皮亚诺算术）中，存在一个不可证明亦不可否证的命题。该证明中引入的“可计算性”观念巧妙地利用了递归函数的概念，实际上构成了可计算性理论的先声。哥德尔对形式系统的技巧——将元数学陈述编码为算术语句——为图灵和丘奇提供了自指构造的模板。不完全性定理还暗示着：不存在一个能判定任何数学命题的真假的通用算法。
5.1.2 图灵、丘奇、波斯特的独立贡献
- 阿隆佐·丘奇（1936年）证明了“自然数上的一阶谓词逻辑的可满足性”不可判定；并借助λ-演算提出了丘奇论题，以递归函数定义可计算性。
- 艾伦·图灵（1936年）发明了图灵机模型，给出了停机问题的不可判定性证明，建立了图灵机可计算函数的概念。他的论文奠定了经典计算理论的基础。
- 埃米尔·波斯特（1936年）独立开发了波斯特系统，并提议了类似丘奇-图灵论点的想法，但起初未受广泛关注。他后来引入了许多一归约的概念，以及不可解度（之后被图灵深入研究为图灵度）。
三人几乎同时但独立地从不同角度定义了可计算性的边界，催生了现代可计算性理论。
5.2 丘奇-图灵论点的哲学争议
丘奇-图灵论点认为：一切直觉上有效的机械计算过程等价于图灵机可计算。哲学上该论点引发了关于“算法”和“有效过程”本质的争论。一些哲学家问：是否存在一种在物理上实现但超越图灵机能力的计算？例如，连续时间模拟计算、量子力学中的非确定计算、宇宙中的热力学过程，均被某些观点认为可能突破图灵机限制。然而，迄今仍未出现一种被公认“有效”的、确实超越图灵机能力的物理/数学过程。该论点一方面是“工作假设”，另一方面也导致了对“超计算”概念的批判性讨论。
5.3 可计算性对数学基础的影响
可计算性彻底改变了对数学真理和可证明性的理解。希尔伯特曾充满信心地认为每个有意义的数学问题都可通过有限步骤的推理得以解决（“我们必须知道，我们必将知道”）。然而，停机问题的不可判定性以及哥德尔的不完全性定理碎片了这种理想。数学中存在本质上“无法通过算法判定”的命题，这意味着数学家不能依赖通用机械方法来解决所有问题。可计算性还揭示了构造性数学的边界：有些函数虽然客观上存在（如某种枚举），却无法被构造性地描述。可计算性理论由此成为数学逻辑和计算机科学交汇的基石。
6 现代拓展与应用
6.1 超计算与量子计算
6.1.1 超计算的概念与争议
超计算（Hypercomputation）泛指那些声称能够计算图灵机无法计算的函数（即不可判定问题）的理论模型。例子包括：
- 无限计算：在无限多步后输出结果（例如用无限长时间求解停机问题）。
- 闭时曲线模型：利用时间旅行反馈来“计算”。
- 某些量子引力模型：尝试利用时空结构进行计算。
多数计算机科学家和物理学家认为超计算不可能在物理现实实现，因为超计算往往需要无限资源或违反物理定律（因果如常）。争议的实质是：丘奇-图灵论点是否应被视为自然规律，还是一个纯粹数学定义。目前为止，多数理论家将它视为关于算法的“最合理假设”，而超计算更多地被视作哲学或科幻。
6.1.2 量子计算与可计算性的关系
量子计算利用量子叠加、纠缠等物理性质，在某些特定的计算问题（如因式分解、搜索）上大大提速（从指数时间降至多项式时间）。然而，量子计算机并没有突破可计算性边界：它仍处于图灵机可计算的范畴之内。也就是说，任何量子算法都可以被经典图灵机在指数时间内模拟（量子计算机只是更快，而不能解决停机问题等不可判定问题）。此外，量子图灵机已经被证明与经典图灵机等价（对可判定性的定义相同）。因此，量子计算和超计算属于不同层次：前者提高效率，后者挑战可计算性的边界。
6.2 可计算性在程序与逻辑中的体现
6.2.1 程序语言的可计算性等价
几乎所有主流的程序语言（C、Java、Python、Haskell等）都支持递归、循环和条件分支，因而它们都是图灵完备的（即可以计算任何图灵机可计算的函数）。不同的语言可能在表达力（如类型系统、闭包、高阶函数）上有所不同，但在可计算性层面是等效的。这意味着：如果一个问题在图灵机上是不可判定的，那么在任何图灵完备的语言中也没有算法能解决它。程序语言的类型系统（如依赖类型）可以限制程序只能写那些总是停机（原始递归）的函数，从而避免某些不可判定问题在类型检查中出现，但这是通过损失通用性达成的。
6.2.2 可判定性在定理证明器中的应用
现代定理证明器（如Coq、Isabelle、Lean）内置了某种形式化逻辑系统，其中的可判定性质（如公式的合取范式（SAT）的某些子集）被用于自动化推理。对于不可判定的逻辑片段，证明器往往依赖用户交互（手动构造证明）或半可判定的搜索策略（如基函数的重写）。举例来说，一阶逻辑的谓词逻辑是不可判定的，但它的有限子集（如无函数符号的Bernays-Schönfinkel片段）却是可判定的，因此可被自动化求解。可计算性理论为定理证明器的设计提供了关键指导：哪些部分可以全自动化？哪些部分必须依赖用户？这保证了证明器的完备性和实用性。
6.3 可计算性与人工智能
6.3.1 学习理论中的可计算性限制
在机器学习和统计学习理论中，一个核心问题是“学习一个概念能否通过算法完成”。可计算性理论告诉我们：存在一些概念类，它们是“可学习的”（按照统计学意义）但并非“可计算的”——即无法通过有效算法（图灵机）来输出一个假设。例如，某些经过恰当编码的布尔函数集在统计上可泛化，但不存在一个算法能从样本中高效找到目标函数。这就是“可学习/可计算分离”的著名结果：计算性限制阻碍了某些直觉上可学习问题的实际求解。这一结果指导着人工智能研究者寻找具有良好计算性质的假设空间。
6.3.2 可计算性与可学习性的对比
可学习性（通常基于概率近似正确学习框架）和可计算性是不同维度的概念：前者关心是否存在一个有效（多项式时间）算法从有限样本中输出一个近似正确的假设；后者关心是否存在一个算法（不计时间）来精确求解函数或判定问题。两者对比的结论是：
- 一些可计算函数（如任意的布尔函数）是不可学习的（因为样本复杂度随输入维度呈指数增长）。
- 一些不可计算函数（如奇偶性函数的随机形式）是可学习的（在统计意义上，无需找到精确函数）。
- 对于许多实际任务，如图像识别，可计算性不是难题，可学习性才是瓶颈，因为要找的假设往往可计算，但样本和计算效率受限制。
这一对比提醒人们：在人工智能中，可计算性只是起点，可学习性和算法效率是更现实的目标。