部分递归函数

“算法”究竟是什么？这个根本问题是计算机科学和数学的核心。严谨地回答它，不仅仅是满足一种理论上的好奇心，更是开启了对形式推理能力以及其内在限制的一种全新理解。在20世纪之前，“可解问题”的概念虽然直观但却模糊不清。可计算性理论的发展提供了一个极其锐利的工具来形式化这一概念，但在这样做的同时，它也揭示了一个充满适定问题（well-posed questions）却没有任何计算机能解答的宇宙。

本文探讨​​部分递归函数​​的概念，它是我们现代计算定义的数学基石。我们将首先深入其原理和机制，考察所有可计算函数如何从一组简单的初始函数和规则构建而成，并证明这种抽象构造如何等价于图灵机的机械模型。在此之后，我们将探索其深刻的应用和跨学科联系，展示该理论如何为问题难度分类提供一种精确的语言，揭示像停机问题这样的不可计算问题的广阔领域，通过克林尼递归定理阐释自指程序的“魔力”，并为逻辑学基础和哥德尔不完备定理带来新的启示。

想象一下，你想要描述什么是“计算”。你可能会想到一位勤奋的办事员，遵循着一本写有非常精确、无歧义规则的书。这位办事员有一条无限长的纸带、一支铅笔和一块橡皮。他们可以读取纸带上的一个符号，写上一个新符号，擦掉一个旧符号，并移动到纸带的下一个或上一个位置。这个简单、机械的画面正是​​图灵机​​的本质——一个优美的抽象，它抓住了我们所说的“算法”的核心。

但这有一个问题。如果规则书的写法导致办事员在处理某些问题时陷入循环，来回移动、擦除和重写，永无止境呢？计算就永远不会结束。这不是模型的失败，而是一个深刻的特性。它告诉我们，我们试图以这种方式计算的任何函数，都可能不会对每个可能的输入都有答案。机器可能会停机并给我们一个值，也可能永远运行下去。这就引出了​​部分函数​​这一关键概念：一个函数对某些输入有定义，而对另一些输入则没有定义。在计算世界中，一个未定义的输出就是一个不停机的过程。

这种以机器为中心的观点非常直观，但它是唯一的方式吗？让我们尝试一种完全不同的方法。

让我们不要想象一台机器，而是像一位手握一套基本构建模块（一种用于创造函数的数学乐高积木）的大师级建造者一样思考。我们能想象到的最简单、最无可争议的函数是什么？

1. ​​零函数​​，$Z(x) = 0$。无论你给它什么，它都返回零。极其简单。
2. ​​后继函数​​，$S(x) = x + 1$。计数的本质。
3. ​​投影函数​​，$U_{i}^{k}(x_{1}, \dots, x_{k}) = x_{i}$。它们只是从输入中挑选一个，忽略其余的。

这些就是我们的“初始函数”，是最基本的砖块。它们显然都是可计算的，并且总能产生一个答案；它们是​​全函数​​。现在，我们能用它们做什么呢？我们有三条构造规则：

• ​​复合：​​ 我们可以将一些函数的输出插入到另一个函数的输入中。这就像将乐高结构连接在一起。如果基础函数是可计算的，那么它们的复合也是可计算的。

• ​​原始递归：​​ 这是一个更强大的工具，是 for 循环的形式化版本。它允许我们基于一个函数紧邻的前一个值来定义它的当前值。例如，要定义加法，我们可以说 $add(x, 0) = x$ 和 $add(x, y+1) = S(add(x, y))$。我们一步步地构建结果。仅使用初始函数、复合和原始递归所能构建的函数称为​​原始递归函数​​。这个函数类非常庞大——它包括加法、乘法、指数运算，以及几乎所有你能想到的、保证会结束的“常规”算法。一个关键特征是，所有原始递归函数都是全函数；它们的计算“循环”总是有界的，因此它们永远不会无限运行。

但这足够了吗？我们仅用这些工具就能计算所有东西吗？答案出人意料：不能。存在一些可计算的全函数，比如著名的阿克曼函数，它们增长得如此惊人地快，以至于无法仅用原始递归来捕捉。我们还缺少最后一件关键的工具。

缺失的部分是进行无界搜索的能力。想象一下你在家里丢了钥匙。你可以进行​​有界搜索​​：检查每个房间、每个抽屉、每个口袋。这可能需要一些时间，但你的房子是有限的。最终，你要么找到钥匙，要么搜遍了所有地方并断定它们不在那儿。你的搜索必将终止。这就是​​有界最小化​​的精神，这个操作总能得到一个全函数，因为搜索空间是有限且事先已知的。

现在想象一下，你在全世界所有的海滩上丢了一粒没有标记的沙子。你可以开始搜索，但无法保证搜索会结束。你也许能找到它，但如果它一开始就不在那里，你的搜索将永远持续下去。这就是​​无界最小化​​，由 ​​μ-算子​​（mu-operator）形式化。其定义如下：

$f(\vec{x}) = \mu y \, [g(\vec{x}, y) = 0]$

这可以读作：“f(x) 是使函数 g(x, y) 等于零的最小的数 y。”为了计算它，我们必须逐一测试 $y=0, y=1, y=2, \dots$，直到找到一个满足条件的 $y$。

这正是部分性（partiality）的灵魂所在。如果存在这样的 $y$，我们的搜索就会停止，函数 $f(\vec{x})$ 就有定义。如果不存在这样的 $y$，搜索将永远进行下去，而 $f(\vec{x})$ 就是未定义的。这恰好对应于我们不停机的图灵机！

我们从初始函数出发，使用复合、原始递归以及这个强大而危险的 μ-算子所能构建的函数类，就是​​部分递归函数​​类。

所以现在我们对计算有了两种看起来截然不同的描述：基于纸带的机械式图灵机和基于构造的抽象式部分递归函数。以下是计算机科学核心的惊人发现：

​​图灵可计算函数类与部分递归函数类是完全相同的。​​

这不是一个哲学陈述，而是一个严谨的数学定理。两条路径通向完全相同的地方。这给了我们巨大的信心，让我们相信我们确实抓住了“计算”的本质。这一点是如此基础，以至于它支撑起了​​丘奇-图灵论题​​——即任何直观、有效的计算方法都可以由图灵机执行（因此也是一个部分递归函数）的信念。所以，如果一位科学家发明了一种新的“Lambda-Integrator”并证明其函数都是部分递归的，我们就知道它的能力并不比我们已有的更强；这只是我们定义稳健性的又一证据。

这种等价性怎么可能成立呢？其证明是模拟的杰作：

1. ​​任何图灵机都可以被一个部分递归函数模拟。​​关键在于将图灵机的整个状态——其内部状态、读写头位置以及其纸带的全部内容——编码成一个巨大的自然数。这被称为​​哥德尔编码​​。机器简单的转移规则（如果你在状态 Q 看到符号 A，就写下符号 B，向右移动，并进入状态 R）变成了一个原始递归函数，它将一个巨大的数字（旧配置）转换为另一个（新配置）。整个计算过程只是一串这样的数字序列。问题“这台机器会停机吗？”变成了“是否存在一个数字 $y$ 编码了一个完整、有效、停机的计算历史？”这正是 μ-算子的完美用武之地！任何图灵机 $e$ 计算的函数都可以写成 $\varphi_e(x) = U(\mu y \, T(e,x,y))$ 的形式，其中 $T$ 是一个原始递归谓词，用于检查 $y$ 是否是机器 $e$ 在输入 $x$ 上的有效停机计算，而 $U$ 是一个原始递归函数，用于从计算代码 $y$ 中提取最终答案。这就是​​克林尼范式定理​​，一个将任何机器转化为部分递归函数的精确配方。

2. ​​任何部分递归函数都可以由一台图灵机计算。​​这个方向更为直接。我们可以为初始函数设计简单的图灵机。我们可以通过物理上连接机器来模拟复合，将一台机器的输出带馈送到下一台的输入带。我们可以用一台机器来模拟原始递归，它使用其纸带的一部分作为循环的计数器。我们还可以模拟 μ-算子，方法是让一台机器系统地尝试 $y=0, y=1, y=2, \dots$，为每个 $y$ 运行一个子机器，直到其中一个产生期望的输出 0。如果永远没有产生，主机器就永远运行下去，完美地模仿了 μ-算子的行为。

将程序编码为数字的想法带来了一个惊人的后果。如果一个程序只是一个数字，那么一个程序就可以将另一个程序作为其输入。这就引出了​​通用函数​​ $U(e,x)$ 或​​通用图灵机​​的概念。这是一个单一、特定的程序，可以模拟任何其他程序 $e$ 在任何输入 $x$ 上的运行。它是最终的解释器。这台机器的蓝图由克林尼范式定理直接给出。

这种将程序视为数据的能力，也由​​s-m-n 定理​​（该定理描述了如何从更通用的程序中算法化地“编译”出专门的程序）形式化，打开了一个潘多拉魔盒。如果程序只是数据，我们就可以提出关于它们的问题。但是我们能构建算法来回答所有这类问题吗？

例如，我们能否编写一个程序，它接收任何其他程序 $e$作为输入，并告诉我们 $\varphi_e$ 是否是一个全函数（即机器 $e$ 是否在所有输入上停机）？这等同于询问是否存在一个全可计算函数可以判定此性质。答案是响亮的“不”。赋予我们通用性的框架本身也施加了根本性的限制。​​莱斯定理​​给出了最终的裁决：关于程序行为（语义）的任何非平凡性质都是​​不可判定的​​。没有通用的算法能够审视一个程序并确定它是否是全函数、是否是常数函数，或者它是否曾输出过数字 0。

这一切都源于部分性的最初种子：不停机的计算。编写一个函数 $g$ 来“补全”任何部分函数 $f$（即当 $f$ 未定义时输出一个像 0 这样的默认值）的梦想是不可能实现的。这样一个函数 $g$ 必须能够预测 $f$ 是否会停机，而这本身就是不可判定的停机问题。无界搜索的力量给了我们通用计算，但代价是，在一般情况下，该计算的行为从根本上变得不可知。

现在我们已经把玩了部分递归函数的机制——看到了它们如何从最简单的模块构建而成，以及它们如何能执行任何可以想象的计算——我们可能会想把它们放回数学家的工具箱里，当作专家的奇珍。但这样做将错失我们整个旅程的意义。这些抽象函数不仅仅是关于计算，它们关乎计算本身的性质。它们提供了一种极其精确的语言，使我们能够提出——并且惊人地能够回答——一些关于知识极限、自指悖论以及逻辑和数学基础的最深刻问题。

理解了原理之后，我们现在转向其推论。我们将看到这个形式化的“算法”模型如何成为一把钥匙，它能打开我们甚至不知道其存在的门，引领我们从计算机科学的实践走向关于证明某事为真的哲学核心。

在可计算性理论出现之前，一个问题要么是“可解的”，要么是“不可解的”，这是一种模糊、直观的感觉。一个人的难题是另一个人的不可能的梦想。部分递归函数给了我们一个极其锐利的工具，用客观的严谨性来对问题进行分类。

想象任何其实例可以由自然数表示的问题。例如，问题“数字 $x$ 是素数吗？”如果存在一个全递归函数——一个保证对每个输入都停机并给出明确“是”或“否”答案的算法——那么一个问题就被认为是​​可判定的​​（或​​递归的​​）。对于素性问题，如果 $x$ 是素数，函数将输出 $1$，否则输出 $0$。对于素数集合 $A$，这个函数被称为​​特征函数​​ $\chi_A$。一个可判定的问题是拥有一个可计算的特征函数的问题：一个从不失败、从不卡住、总能给出正确答案的完美预言机。

但是那些更棘手的问题呢？考虑一下病毒扫描程序的任务。它寻找会执行恶意行为的程序。扫描程序可以在一个安全的“沙盒”环境中运行一个程序，看看它是否会做坏事。如果它做了，扫描程序可以自信地将该程序标记为“恶意的”。但如果它没有做呢？是它还没有做任何恶意的事情，还是它永远不会做任何恶意的事情？扫描程序不能永远等待以找出答案。

这就引出了第二类极其重要的问题：​​半可判定的​​问题，其形式化名称为​​递归可枚举​​（r.e.）集。对于这样的集合，我们没有一个完美的预言机，但我们有一个“证明检查器”。存在一个部分递归函数，如果一个输入在该集合中，它就会停机（比如输出1），但如果不在，它就会永远运行下去。这就像一个只会回答“是”的预言机。一个“否”的答案由永恒而令人沮丧的沉默来表示。所有在给定输入上最终会停机的程序的集合，是半可判定问题的一个经典例子。你可以通过运行它来确定它是否停机——如果它停了，你就知道了。如果它不停，你将永远等待。

这种源于部分函数简单定义的区别，为宇宙中所有问题创造了一个基本的难度层次结构。有些问题是清晰可判定的。另一些是半可判定的，我们可以验证“是”的答案，但可能在试图确定“否”时陷入困境。而正如我们即将看到的，有些问题是如此困难，以至于它们甚至不具备这种性质。

几个世纪以来，数学家们相信，任何提得好的问题都必须有一个原则上可以通过计算找到的答案。部分递归函数理论对这一信念给予了令人震惊和革命性的打击：存在一些问题，是任何算法、任何计算机，无论多么强大或聪明，都永远无法解决的。

其中最著名的是​​停机问题​​。问题很简单：给定任意程序 $e$ 的代码和一个输入 $x$，程序 $\varphi_e$ 在 $x$ 上运行时最终会停机吗？人们可能认为我们可以简单地模拟该程序，然后看看结果。但如果程序不停机，我们的模拟将永远运行下去，我们永远无法确定。我们想要的是一个通用的判定器，一个函数 Halts(e, x)，它总能返回真或假。

该理论以铁证如山的方式证明，不存在这样的全递归函数。其中一个特别具有毁灭性的版本是“对角”停机问题，它问：代码为 $x$ 的程序在以其自身代码为输入时是否停机？这类数字的集合，通常称为 $K = \{x \in \mathbb{N} : \varphi_{x}(x) \downarrow\}$，是典型的半可判定但不可判定的集合。它是半可判定的，因为我们可以构建一个通用模拟器来测试 $\varphi_x(x)$，如果模拟停机，它就停机。但它不可能是可判定的。如果它是，我们就可以构造一个矛盾的程序，它当且仅当它不停机时才停机——这是一个逻辑上的不可能。

这不仅仅是一个孤立的、深奥的悖论。它是巨大冰山的一角。​​莱斯定理​​揭示了不可计算问题的全部惊人范围。其本质是说，程序行为的任何有趣的、非平凡的性质都是不可判定的。程序的“行为”（或*外延）是它所计算的内容——即其输入-输出映射——与其代码（其内涵*）相对 [@problem_-id:3045828]。

一个程序的停机输入域是有限的吗？不可判定。一个程序是否曾输出过数字42？不可判定。一个程序计算的函数是全函数（即在所有输入上都停机）吗？不可判定。两个看起来不同的程序在行为上是否实际上是等价的？不可判定。计算世界被无数这样定义完美却算法上无法回答的问题所困扰。这一发现从根本上改变了我们对形式系统力量以及更重要的其内在局限性的理解。

正当这个理论似乎全是关于局限性的时候，它却给我们带来了一个如此强大和反直觉以至于感觉像是魔术的结果：​​克林尼递归定理​​。这是一个关于自引用的定理，而且是能够奏效的自引用。

该定理的一种形式指出，对于任何转换程序代码的全递归函数 $F$，都存在某个程序代码 $e$，它是 $F$ 的一个“不动点”。这并不意味着 $e = F(e)$，对于像 $F(e) = e+1$ 这样的函数，这显然是错误的。它的意思是，代码为 $e$ 的程序所计算的函数与代码为 $F(e)$ 的程序所计算的函数相同。换句话说，$\varphi_e = \varphi_{F(e)}$。程序 $e$ 的行为与其自身转换后的版本完全一样。

这在实践中意味着什么？这意味着可以编写出能够操作自身代码的程序，而无需事先知道该代码！

对此最著名的演示是 ​​quine​​，一个运行时会打印出自身源代码的程序。这似乎是不可能的。一个程序要打印自己的代码，它必须在自身内部包含该代码。但如果它包含了它的代码，那会使程序变长，这意味着它所包含的代码现在是错误的……如此无限循环下去。

递归定理展示了如何打破这个循环。其证明是构造性的，并且异常巧妙。它涉及创建一个包含两部分的程序。第一部分是一个“模板”，它知道如何获取一段代码并将其打印两次，一次作为字面数据，一次作为可执行代码。第二部分是那个模板本身的代码。该定理保证你可以找到一个程序的索引，该程序基本上是在说：“这是一个程序的蓝图 $B$。现在，用它自己的蓝图 $B$ 作为输入来执行 $B$。”结果就是程序打印出它完整的自身。

这远不止是一个派对戏法。这个原理是任何能够分析、修改或复制自身的程序的数学基础。计算机病毒是自复制程序，是递归定理在现实世界中的一个（尽管是恶意的）体现。能够编译自身源代码的编译器（一个称为“自举”的过程）也依赖于这种计算自引用的深刻原理。

也许最深刻的联系是计算与数学基础之间的联系。部分递归函数理论为20世纪最伟大的智力成就之一——哥德尔不完备定理——提供了一条全新且异常清晰的路径。

这种联系是通过​​算术化​​建立的。正如我们可以为每个可计算函数分配一个数字（一个索引），我们也可以使用哥德尔编码为像​​皮亚诺算术（PA）​​这样的形式系统中的每个公式、公理和证明分配一个唯一的数字。这意味着关于数学的陈述（例如，“这个公式是可证明的”）变成了数学内部的陈述（例如，“存在一个具有性质 $P$ 的数字”）。

关键的洞见在于，任何部分递归函数的图——其（输入，输出）对的集合——都可以由算术中一种非常简单的公式类型来定义，称为 $\Sigma_1$ 公式。$\Sigma_1$ 公式断言了某个具有简单、可检查性质的事物的存在。具体来说，“$f(x) = y$”这个陈述等价于“存在一个数字 $t$，它编码了函数 $f$ 在输入 $x$ 上产生输出 $y$ 的有效、分步计算过程”。令人惊奇的是，“是一个有效的计算轨迹”这个性质是原始递归的，这意味着它非常简单，以至于 PA 可以轻松地对其进行推理。

因此，PA 足够强大，可以证明任何为真的 $\Sigma_1$ 语句。所以，如果一个程序停机，PA 可以通过形式化地验证其计算轨迹来证明它停机。现在，再次考虑停机问题。如果 PA 是一个“完备”的理论——也就是说，如果它能证明或证伪其语言中的每一个陈述——那么它就应该能判定停机问题。如何做到？要确定程序 $e$ 在输入 $x$ 上是否停机，我们可以开始搜索 PA 中所有可能的证明。如果它停机，我们最终会找到一个它停机的证明。如果它不停机，我们最终会找到一个它不停机的证明。

但我们已经知道停机问题是不可判定的！没有算法能判定它。由于搜索证明是一个算法过程，这意味着我们的假设必定是错误的。PA 不可能是完备的。必定存在关于数字的真陈述（具体来说，是关于不停机计算的真陈述），在该系统内是不可证明的。计算的极限投下了一道长长的阴影，揭示了形式证明的内在局限。

这种联系甚至更深，触及了“证明”究竟是什么的哲学。在经典逻辑中，一个陈述要么为真要么为假，无论我们是否能证明它。但在​​构造主义​​或​​直觉主义逻辑​​中，真理与可证明性联系在一起。证明一个陈述就是构造一个作为其证据的对象。

在 ​​Brouwer-Heyting-Kolmogorov (BHK) 解释​​下，逻辑连接词的意义是通过这种构造或“实现元”（realizers）来给出的。例如：

• $A \land B$ 的一个实现元是一个序对 $\langle a,b \rangle$，其中 $a$ 是 $A$ 的实现元，$b$ 是 $B$ 的实现元。
• $A \to B$ 的一个实现元是一个过程，它能将 $A$ 的任何实现元转换为 $B$ 的一个实现元。

一个“转换……的过程”。这听起来很熟悉！这正是部分递归函数的工作。在​​克林尼可实现性​​中，这个想法被形式化了：实现元是自然数，而“过程”是它们所代表的部分递归函数。一个索引 $e$ 实现蕴涵 $A \to B$，如果函数 $\varphi_e$ 接受 $A$ 的任何证明的代码，并计算出 $B$ 的一个证明的代码。

这就产生了一个惊人的对应关系，称为​​柯里-霍华德同构​​，存在于逻辑与计算之间。逻辑中的命题对应于编程语言中的数据类型，而证明对应于程序。一个函数的类型签名，如 (integer) -> (string)，是一个命题，而该函数的代码是该命题的一个构造性证明。这一洞见对计算机科学产生了巨大影响，特别是在编程语言和自动证明助手的设计中，编写程序和证明定理成为了同一枚硬币的两面。

我们对部分递归函数的探索带领我们进行了一场非凡的智力冒险。起初只是一个定义“算法”的形式化练习，最终却将我们引向了计算机科学、数学和哲学的最前沿。它向我们展示了我们通过计算和形式推理所能知道的深刻极限，同时又交给我们强大的自引用工具，这些工具似乎又在挑战这些极限。在这些函数朴素的美感中，我们发现了思想本身基本结构的一种反映。