五度妙笔
企业透视镜
API商城
数据库张江：图灵机“升仙记” ——从神谕到超代数谱系
单击上方“图灵人工智能”，选择“星标”公众号
您想知道的人工智能干货，第一时间送达
导语
如果把普通图灵机看作困于“凡间”的修士，那么神谕就是能够瞬间回答不可判定问题的大神，神谕图灵机则是掌握了“请神术”的修行者。每经历一次图灵跳，机器便突破当前计算层级的能力边界，向更高一重“天界”飞升；而当有限次迭代继续延伸至超限序数，计算对象从自然数升级为函数与泛函，逻辑量词也开始遍历更高类型的对象，高阶递归论的仙界图景便逐渐展开。本文借助一套贯穿始终的修仙隐喻，从停机问题与对角线构造出发，依次讲解神谕、图灵归约、图灵跳、可计算序数、Kleene S1–S9 高阶递归以及算术与解析谱系，并最终抵达三条“升仙路径”交汇之处——超算术集合。抽象的计算理论，也由此化作一场层层破境、不断逼近无穷的思想远游。
关键词：图灵机、停机问题、神谕图灵机、对角线构造、图灵归约、图灵跳、高阶递归论、可计算序数、超限递归、算术谱系、解析谱系、超算术集合
最近为了搞清楚Kleene第二递归定理的来龙去脉，开始接触神谕、神谕图灵机、图灵跳、高阶递归论、超算术集合等概念。这些都是发展自20世纪40-50年代的理论，是对经典计算理论、递归论的进一步扩展。
图灵机和经典递归论奠定了我们今天所使用计算机的基础原理，而有趣的是，神谕、图灵跳等高阶的理论其实在现实世界没有对应物。但是，理论家们却凭空造出这些概念来，试图用人类有限的意识来窥探无穷的世界。
于是，我突然有了一个创意：这些涉及到无穷递归、无穷序数的概念仿佛就是神仙国度中的存在，那么随着一步步的图灵跳跃和概念提升，我们就可以把递归理论一步步地从普通凡间推广到神仙国度。这便有了这篇文章的创意来源。于是，神谕就是大神，神谕图灵机就是会请神术的修士，不停的图灵跳就是一级级的升仙过程……。
本文借用修仙、仙界的比喻来诠释高阶递归论，下表把神话意象和严格的计算理论概念一一对应，阅读正文遇到比喻时可以回来查阅，做到一眼分清隐喻与数学定义。
| 神谕 Oracle | ||
| 神谕图灵机（Oracle Turing Machine） | ||
| 图灵跳 Turing Jump | ||
| 超限递归、可计算序数、丘奇‑克莱尼序数 | ||
| Kleene 超算术三等价定理 | ||
凡间——图灵机的王国
凡间——图灵机的王国
首先，让我们先从回顾凡间世界的基本概念——图灵机开始。
图灵机
你应该知道，所谓的凡间就是图灵机的王国，这是因为今天我们使用的一切计算机都可以归结为图灵机这个原型。图灵机（Turing Machine）由艾伦・图灵（Alan Turing）于1936 年提出，它由一条无限长的纸带、读写头、内部状态集合以及有限的转移规则构成：纸带被分割成一个个方格，可以书写符号；读写头可以左右移动、读取或改写纸带上的符号；机器根据当前状态与读到的符号，查找转移表，决定改写符号、移动方向以及下一状态。机器没有预置的硬件算法，全部计算行为由有限的转移规则描述。
图灵机的死穴——图灵停机问题
图灵机功能强大，实际上无论是今天最强大的AI算法还是你手头的笔记本电脑都是图灵机的某种实现。然而，图灵机却有一个死穴，这就是图灵停机问题。你是否可以写出一个程序，让它帮你判断任意一台特定编码（一般图灵机可以被编码为自然数，或者等价地，你也可以把理解为源代码）的图灵机作用到数据上是否会停机？
这一问题的答案是，程序根本就不存在。为什么呢？
第一次“通神”——对角线构造论证图灵停机问题不可解
要论证判定任意图灵机作用到任意数据是否会停机的程序不存在，我们需要借助自指法，也就是大名鼎鼎的“对角线构造”方法。这一方法最早被乔治·康托尔（George Cantor）发明，用于论证实数比自然数更多；后来又被罗素（Bertrand Russel）拿来构造了“罗素悖论”，直接引爆了第三次数学危机；再后来，哥德尔（Kurt Godel）又用它证明了“哥德尔不完备性定理”。这一方法用人类有限的智慧，洞悉到了无穷世界（神仙国度）的根本奥秘，因此，我把这种方法称为第一次“通神”。
真正论证图灵停机问题在图灵机范围内不可解的手段是通过反证法，假设这样的判定机器存在，然后利用自指程序调用，引发矛盾。
具体做法如下：假设判定任何图灵机作用到上停机的程序存在。那么，我总能通过调用造出一个程序：
function Q(x,y){
z=U(x,y);
if(z=True){
do while(True){
}
}else{
return;
}
}
于是，当你把自身的代码既做代码（）又做数据（），从而把喂给的时候，这一步就是自指（也叫对角线构造，diagonalization），它会引发矛盾。
如果返回的是True，则程序会陷入死循环；
否则，如果返回的是False，则直接返回（停机）。
也就是说，如果判断作用到自身代码上停机，则实际的运行就不停机，否则如果判断不停机，就停机。因此，我们可以证明，这样的判断任意机器作用到任意数据的程序不存在。
图灵停机问题的不可解（不可判定性）让我们看到了图灵机能力的极限。
神谕与“请神术”
怎么办呢？图灵给出的答案就是“请神”！通过在普通图灵机中加一条特殊指令——神谕(Oracle)，就能让普通图灵机可以直接通神。
对于停机问题来说，神谕可以直接给出你当图灵机作用到数据上是否会停下来的答案，而且保证答案是正确的。其实，在上面论证图灵停机问题中的那个假想的程序就是一个神谕。你可以把神谕理解为一个神，一个上帝，它能够在瞬间给出任意图灵机作用到上是否停机的答案，而不需要执行我们凡人（图灵机）意义上的任何计算过程。这也是为什么我说上述论证为第一次“通神”的原因。
神谕图灵机（也叫神谕机）就是一个配备了神谕的图灵机。如图所示：
和图灵机一样，神谕图灵机依旧拥有纸带、读写头与有限转移规则，但新增一类特殊查询指令：机器可以把一个自然数写在查询纸带上，向神谕发起询问；神谕立刻输出布尔结果 0 或 1，即作用于是否会停机。不难看出，上述通过调用构造的程序就是一台神谕图灵机。
神谕图灵机是图灵在 1939 年引入的扩展模型，用来研究相对可计算性。借助神谕机，我们可以站在更高的视角重新审视停机问题：在普通图灵机上不可解的停机问题，可以借助外部神谕得到解答。
你可以把图灵机看作一个普通的修士，而神谕图灵机就相当于是一个学会了请神术的修士。打不过的时候，神谕图灵机就可以直接请神上身（调用神谕）。
再论图灵停机问题
让我们再来看图灵停机问题。在前面的论证里，我们假设是一台普通的图灵机，因而通过构造引发矛盾，证明不存在。
但有了神谕和神谕图灵机的概念，我们知道，其实就是一个神谕，而也不再是普通图灵机器，而是神谕机器。因此，从另一个视角看，对角线构造那段自指程序其实揭示的更深层次的事实是：神谕图灵机和图灵机压根就不是一个类别。在图灵机范围内不可解的问题，在神谕图灵机的范围内是完全可解的。
因此我们可以换一个视角理解这个证明：它论证了普通图灵机无法实现停机判定程序，但并没有否定作为外部黑盒（神谕）的可能性。
当我们假设了存在以后，我们就能判定任意图灵机作用到上是否停机，但并没有说一台神谕图灵机作用到上会怎样。这就是问题的关键之所在。如果我们假设神谕图灵机压根就不是一台图灵机，那么也就无法正确得到它作用到数据上的停机判断了，因此也就没法将的代码进行自指带入这回事儿，也就不会引发任何矛盾。
所以，自指构造否证的不是神谕的存在性，而是告诉我们，神谕图灵机必须和图灵机不在同一个类别。
请神术的弊端与升级
请神术的弊端与升级
由此可见，图灵机和神谕图灵机是两类不同能力的机器。通过引入神谕，神谕图灵机是对图灵机的一次升级，这样神谕图灵机就可以求解图灵机停机问题了。通俗地说，学会了请神术的修士不能等同于普通修士看待，他完全可以破解图灵停机问题。
修士之间的能力比较——图灵归约关系
学会了请神术的修士可以退化为普通修士，而普通修士很难在短时间内学会请神术。同样的，任何图灵机可解的问题总是可以被神谕图灵机轻松求解，但反过来却不行。
为什么呢？首先，神谕机器可以轻松退化为普通图灵机，你在神谕机中不去调用神谕就好了，所以它当然能解决图灵机可解的任何问题。就相当于普通修士可以不去使用请神术，他也是一名合格的修士。
但是反过来，神谕图灵机可求解的问题却不一定能被图灵机求解。最典型的就是停机问题。神谕图灵机轻松调用神谕就能判定是否停机，普通图灵机就没有这个本事了。怎么把这种修士之间的能力比较用数学说明白呢？
这就牵扯出了一个重要的概念：图灵归约，简称归约（reduction）。一般地，我们称集合可以归约为，记为：
是指存在某个图灵机（指标为e），使得，是 A 的特征函数：
表示：以 为神谕的第 号图灵机，输入 的输出。换句话说，只要图灵机可以以为神谕，那么它就能判定一个元素是否属于。
如果，但是不成立，则，称为严格归约为。
因此，如果我们把任何一个图灵机可解的问题看作是一个集合，即的特征函数是图灵可计算的，是停机问题的集合（即当图灵机作用到上停机，则，这里代表的是将数对编码为一个自然数，例如我可以用作为这个编码函数。那么给定一对，例如，我们就可以计算出图灵机作用到数据上这个事件的编码为：）。因此，任意图灵可计算的问题都可以由配备了神谕的神谕图灵机进行求解，但反之则不行这件事儿，就可以表达为归约关系：。
如果且，则，即与等价。
正如图灵机可以有无穷多个，但是它们的能力彼此等价；同样，配备了神谕的图灵机（这里特指一阶神谕图灵机，以区别于后面引出的高阶神谕图灵机）也有无穷多个，但它们的能力也是彼此等价的。这件事儿就可以用关系来表达。
很多图灵机不可求解的问题所对应的集合都可以等价于图灵停机集合。这也就意味着，配备了图灵停机问题神谕（也就是这个程序）的神谕机可以求解所有这些图灵不可解的问题，这是因为你可以像程序的构造那样，在程序中加入任意的代码，从而把问题转化为的判定结果上。这样只要给出了求解答案，那个问题也就自然解决掉了。
所以，你不需要关心张三问题的神谕，李四问题的神谕图灵机，你只需要关注一种神谕，和一种神谕图灵机，我们统一记为就好了，它表示以图灵停机问题为神谕的神谕图灵机。这样的记号在后面会看到用场。
那么， 是否这个神谕图灵机就是所有机器能力的上限了呢？我们有没有可能再根据对角线技术来发现神谕图灵机的能力极限呢？事实上，神谕图灵机也不是万能的，它有它的能力极限，而正是根据这个极限，我们能够引入更高阶的神谕和神谕图灵机，从而引发一个无穷的跃迁过程，如下图所示：
请神术的能力极限——神谕图灵机的停机问题
学会了请神术并不等价于成为神仙，请神术也有其能力边界。
事实上，即使有了神谕机，我们仍然可以利用自指逻辑找到它的能力边界。首先，我们要讨论一个神谕图灵机的编码问题。图灵机都可以被一个自然数编码，那么，神谕图灵机能否也可以被自然数编码呢？
由于调用神谕这个操作完全可以看作是一条特殊的命令，因此，中的所有的神谕图灵机也和图灵机一样可以被自然数编码，我们统一把神谕机的编码记为，它是一个自然数，代表的是以为神谕的神谕机器的编码。那么，我们自然也可以构造类似图灵停机的问题：任意一个编码为的神谕图灵机，作用到数据上会停机吗？这就是属于神谕图灵机类的停机问题。
同样地，我们构造一个神谕机，它可以返回神谕机作用到上是否停机的结果。于是，你只需要把之前图灵判定问题代码中的改为就可以了。新的程序不妨叫做，其代码如下：
function Q'(u,y){
z=O(u,y);
if(z=True){
do while(True){
}
}else{
return;
}
}
那么，图灵停机问题的自指论证逻辑可以搬过来，不是否证这个程序的存在性，而是意识到原来它是更高一阶的神谕，而这个程序则是更高一阶的神谕图灵机。它不在神谕图灵机这个类别中，而是判定神谕图灵机类是否停机的二阶神谕图灵机。
这就有意思了。我们回顾一下我们都做了什么。我们从普通的图灵机出发，发现图灵机类存在着一类不可解的问题：图灵停机问题。从而为了求解它，我们引出了该问题的神谕，于是图灵停机问题可解了，我们还可以得到神谕图灵机类。但是，类也有它的停机问题，于是为了求解它，我们又引出了高一阶的神谕，以及更高一阶的神谕图灵机。结果同样的自指逻辑发现又是比神谕图灵机高一个层次的机器。这样的逻辑显然可以无限延伸下去……。
这就自然而然地引出了图灵跳的概念。
仙界的三十三重天——图灵跳与“递归升仙”
传说仙界也是分为不同等级的，总共有“三十三重天”，层次越高的神仙生存在越高的天界。修士要想从下面的天界飞升到上面的天界，就要学会一个特殊本领——图灵跳。
不严格地讲，你完全可以把图灵跳理解为一个动词，即从低级别的神谕图灵机构建高级别的神谕图灵机的这一操作。但是，严格的图灵跳定义为一个自然数的子集。
图灵跳（Turing Jump）定义为：给定一个自然数的子集合，那么，相对于的图灵跳（读作 A-prime），也是一个自然数的子集，定义为所有以 A 为神谕的神谕图灵机能够停机的集合：
这里，代表的是由一对自然数编码而成的自然数；代表以为神谕的图灵机，为该神谕图灵机的编码；为输入给的数据。于是，就称为的图灵跳。
你可以验证一下前面给出来的各种图灵机和神谕图灵机的例子。
当的时候，这个时候就是停机集合，也就是的全部编码的结果。
当的时候，也就是是“图灵停机问题集合”这个神谕，此时，就是所有的以为神谕的神谕图灵机对应的停机集合。
进一步，如果我们取的时候，就是以为神谕的神谕图灵机对应的停机集合
……
这个定义是非常一般的定义，无论你是哪一个层次的神谕，和神谕图灵机，我总能根据这个定义得到更高一层次的神谕图灵机。因此，该定义具有相当的普适性。从空集开始，我们可以排列出所有的在停机问题集上的图灵跳：
，即图灵机的停机集合，即一阶图灵跳，为一阶神谕图灵机；
，即一阶神谕图灵机的停机集合，即二阶图灵跳，为二阶神谕图灵机；
，即二阶神谕图灵机的停机集合，即三阶图灵跳，为三阶神谕图灵机；
，即阶神谕图灵机的停机集合，即阶图灵跳，为阶神谕图灵机；
注意到，每一步图灵跳，其实你都会得到一个更加精细化的自然数的子集。是一个自然数子集，也是一个自然数子集，也是一个自然数子集，……。
并且，任意的两个子集之间满足：，这里代表的是严格的归约关系。
升仙的三条路径
升仙的三条路径
前面的讨论想必已经让你领略到一个普通的修士（图灵机）是如何通过图灵跳一步步地上升为越来越高层次的仙界的（越来越高阶的神谕图灵机）。然而，即使这一次次的图灵跳，仍然不能让修士彻底转化为彻底的神仙，这是因为修士有一个最大的羁绊：他吃的食物（包括输入的数据，和递归定义所使用的数字）还是普通的“人间美味”（自然数）。于是，要想得到程序，他必须了却人间因果的纠缠。
怎么摆脱呢？上天给了修士三条不同的升仙路径：
第一条，把迭代指标扩展到序数，并推广到无穷大。递归论本身建立在自然数的递归之上，将迭代指标拓展至超限序数，就可以把递归本身拓展到超限递归。
第二条，改变计算所操作的对象类型：计算的输入不再仅限于自然数，进一步允许自然数上的函数，乃至更高阶的泛函参与计算。这一条可以彻底断除人间烟火和因果纠缠。
第三条，从集合与谓词的逻辑定义出发，扩充量词的取值范围，从只量化自然数，拓展到量化函数对象。
有趣的是，Kleene 证明：这三条看上去完全不一样的升仙路径，本质上可以刻画出是同一类集合 —— 超算术集合 ，因此，三者在一定意义上是互相等价的。
第一条路：指标的升级——序数理论
序数（Ordinal Number）理论最早是19 世纪 70‑80 年代由乔治・康托尔（Georg Cantor）创立的。他当时在研究实数集合、无穷点集，需要描述无穷集合的良序结构。集合的基数（Cardinal Number）能够回答：集合有多大的问题；而序数则回答：集合按顺序排起来是什么样子的问题。后来，冯诺伊曼（von Neumann）将序数严格建立在集合的基础上，这也是现代人们常用的序数定义方式。本质上讲，所谓的序数就是保留自然数的序关系，从而扩展自然数集合到更大的数类上的一种尝试。
序数的定义
1923年冯·诺依曼给出现在教科书通用的序数的集合定义法：
首先，自然数都是序数。冯诺伊曼将每个自然数定义为一个集合：
一般地，对于任意的自然数，我们有：
于是，冯诺伊曼可以定义超限序数：
这样，我们不仅可以把全体自然数排序起来，我们还可以继续往后排这些序数：。
这里，
：超限序数，也是最小的无穷序数，排在全体有限自然数 的后面。
：定义为 的后继，在之后再走一步；
，无穷多无穷序数继续往后延伸。
总结来看，为了通过前面的序数扩展出新的序数，我们有两种手段：
后继序数：如果存在直接的前一个序数 ，那么，就存在着后继序数，写作 。它代表“在前一步结果之上，再执行一次操作”。例如 都是后继序数。后继序数本质上讲就是通过迭代+1扩大序数类。
极限序数：这种序数没有直接的前驱，它被定义为前面一整串序数序列的上界/极限。其中， 就是最小的极限序数，它是所有有限自然数的极限。极限序数本质上就是通过求极限的过程而扩大序数类。
可计算序数与
序数是无穷无尽的，但不是每一个无穷序数，都能被有限的算法、有限的字符串来表示。所以，我们要讨论的序数，集中在一个子类别中，叫做可计算序数。所谓的可计算序数，是指存在一套自然数编码的记号系统，可以用算法描述对应的良序结构。所有有限自然数都是可计算序数； 等许多无穷序数同样是可计算序数。
把所有可计算序数收集起来，取它们的上确界，就得到丘奇‑克莱尼（Church-Kleene）序数：，这里的 是最小的不可计算序数：任意满足 的序数都是可计算序数；而 本身不能被任何算法记号表示。
超限递归
引入无穷序数的一个作用就是将我们常用的递归操作扩展到无穷。普通递归（数学归纳）只能在自然数上做有限次迭代：，只能处理有限多步。有了序数之后，我们可以把迭代拓展到无穷序数，得到超限递归（transfinite recursion）。简单讲：超限递归允许我们完成无穷多步迭代之后，仍然可以继续定义、继续往后走。
使用超限递归时，序数分三种情况分别处理：
零序数（起点 ）
给出初始值，和普通递归的起点一样。
后继序数
已经得到了 对应的结果，那么 的结果就由 的结果计算得到。这和普通递归“由前一步算后一步”逻辑相同。
极限序数（例如 ）
极限序数没有直接的前一个序数。以 为例，不存在某个最大的自然数 满足 。它的前面有无穷多个已经构造完成的结果。极限位置的取值，需要参考前面全部无穷多步的结果，而不是只依赖某单一前一步。
对比：
普通递归：只有起点、后继，只能处理有限步；
超限递归：增加了极限序数的处理规则，因此可以跨越无穷继续迭代。
沿序数迭代图灵跳
作为超限递归的一个例子，我们可以扩展图灵跳的概念到“仙界”。前面，我们已经介绍了图灵跳：给定一个集合，它的图灵跳 是编码了“相对于停机的所有图灵机和数据”的自然数集合。从空集开始，我们可以反复做图灵跳：: 迭代0次、1次、2次、3次……迭代次数用普通自然数标记。自然数可以标记任意有限次迭代，但自然数全部用完之后，我们依然希望继续“再迭代一步”。普通自然数就不够用了……。
为了把迭代下标扩展到“仙界”，我们把下标的数域扩展到包含无穷序数，于是图灵跳就可以被扩充到“仙界”，即从有限自然数拓展到所有可计算序数。
定义序数迭代图灵跳 ：
初始步：
后继序数 ：对上一层结果做一次图灵跳
极限序数 ：把所有更早的迭代结果归并到一起（直和）：这里，的含义是将一对自然数编码为一个自然数(这里是简化写法，原则上讲序数不能直接与自然数配对，实际用 Kleene 记号（自然数）来代表序数,而不能直接用)。相当于一个自然数的集合，它的每一个元素对应了一对，其中为比小的序数，为图灵跳中的任意一个元素。所以相当于把所有的比小的图灵跳合并起来（不是取并集）。
这样，对每一个可计算序数 ，我们都得到一个对应的集合 。
注意：本身不是可计算序数，因此我们的迭代只能进行到所有严格小于它的序数，不能抵达 这一层。
超限归纳（Transfinite Induction）
引入无穷序数的另外一个作用就是进行超限归纳。超限归纳是普通数学归纳法向全部序数的推广，可以对无穷序数做证明。
设 是关于序数 的命题。要证明对所有序数 ， 成立，只需证明：如果对所有满足 的序数 ，都有 ，那么 成立。
实际证明时常拆分为三种情形：
零序数 ：验证基础情形 ；
后继序数 ：假设 成立，推证 ；
极限序数 ：假设对全部 有 ，推证 。
普通自然数归纳，等价于超限归纳去掉极限序数分支。
良基归纳（更一般形式）
超限归纳是良基归纳的特例。只要集合上的关系 是良基的（即偏序关系存在最小元），就可以使用良基归纳：
若对所有 都有 ，则 成立，即可得到全部 满足 。
序数上的 是良基关系；良基计算树上按节点高度做归纳，也是良基归纳。
注意区分一下： 超限归纳：用来证明命题；超限递归：用来定义/构造对象，例如超限图灵跳 。
第二条路：对象升级
到此为止，我们讨论的是迭代指标本身的升级，它可以扩展到无穷序数。然而，这一扩展还不算彻底，为了彻底让计算、递归等概念扩展到仙界，我们还需要对处理的对象升级，即图灵机的处理数据的升级。
前面讨论的所有的图灵机，无论是否配备了神谕，都是对自然数的处理。在递归函数论中，这类对象被称为Type-0对象。接下来，我们要对讨论的对象升级，从Type-0对象过渡到Type-1对象。那么，什么是Type-1对象呢？
Type-1 对象（1 型对象），指的是从自然数到自然数的全函数，也就是形如的映射。你完全可以把它直观理解成一条无限长的序列：，每一个位置上都是一个自然数，长度无穷无尽。
所有这样的无穷序列放在一起，就构成了贝尔空间（Baire Space，通常记为：），因此 Type-1 对象也可以说是贝尔空间中的一个点。
既然Type-1对象本质上是由以Type-0对象作为输入点的函数，那么，我们可以以Type-1对象作为输入，定义一种更高阶的函数，这就构成了Type-2对象。
具体地说，Type-2对象是一种泛函，它的输入是 Type‑1 对象（整条无穷序列），输出 是Type‑0 类型的自然数：.
进一步，我们还可以依葫芦画瓢继续升级。既然Type-2对象是一种以Type-1对象作为输入，以Type-0对象作为输出的泛函，那么Type-3对象就是一种以Type-2对象作为输入，以Type-0对象作为输出的泛函，可以记为：
同样，可以定义Type-4对象：
……
于是，我们又得到了一种无穷升级。
神谕的升级
既然输入的点被升级了，那么对点进行处理的神谕图灵机也要升级。神谕图灵机中最关键的部件自然就是神谕了，因此，我们需要先把神谕如何一步步升级说清楚。
在前面的定义中，神谕被定义为一个自然数的集合。这种自然数的集合又可以被刻画为一个特征函数。所以，我们可以把神谕看作是一个函数。当输入对象从升级为, 以及,……，神谕也可以自然跟着升级。
一般的，Type-k类型的神谕就是一个Type-k类型的对象，也就是由Type-(k-1)为输入，以自然数集作为输出的泛函。
这样，我们前面讨论的全部神谕，都是一个Type-0对象，即自然数上的函数，它可以把任意一个自然数赋予0或者1，即是否停机。
Type-1类型的神谕就是一个Type-1型泛函，它把一个Type-0对象，即一个自然数映射为一个自然数。
Type-2类型的神谕就是一个Type-2型泛函，它把一个Type-1型对象，即一个自然数无穷序列到自然数上映射的泛函映射到自然数上。
……
作为一个Type-2神谕的例子，人们常用如下神谕：
其中，为一个Type-1对象，即一个上的泛函。
断除人间烟火与成仙
前面，我们将神谕图灵机定义为配备了神谕的图灵机，即在图灵机中增加一个特殊的操作，即访问神谕。于是，既然我们已经把神谕扩展到了任意Type-k类型，那么，能不能将Type-k类型神谕插入到图灵机模型中，从而定义Type-k型图灵机呢？
答案是否定的。也就是说，即使学会了请神术，而且能够请三十三重天的大神，修士还是普通人，而不是神仙。为什么呢？
这就是因为学了请神术的修士仍然没有断除人间烟火。
Type-k型神谕的输入数据是Type-(k-1)型对象，而在k>=2的条件下，输入数据就不再是图灵机能处理的类型了。回想一下，图灵机能接受的数据全部都写在纸带上，而这条纸带只能存放有限符号的对象，完全存放不了Type-1以上的高阶对象，因此图灵机也自然不能把这种对象传递给神谕。
所以，（Type‑2、Type‑3……）：标准递归论中没有 “k 阶神谕图灵机”。
于是，数学家们给出了不同的图灵机真正成仙的方案，主要思路有如下几种：
放弃纸带机器，改用递归函数模式（这就是Kleene的 S1‑S9 高阶递归理论）
保留图灵机硬件图景，但把实参编码为程序索引（“索引调用” 的假想机器）
-- 核心做法是：机器仍然是普通纸带图灵机；当要调用 Type‑k 神谕，不在纸带上写无穷对象，而是把生成该高阶对象的子计算的程序索引 e₀（一个自然数）写到查询纸带，神谕拿到索引，按索引语义得到高阶对象。
不往更高对象类型走，改用超限时间 / 超限纸带（序数图灵机、无限时间图灵机 ITTM）
面向连续对象的机器模型（Weihrauch Type‑2 有效机器 T2EM，可计算分析）
在这些理论中，Kleene的S1-S9高阶递归理论更能兼容各种类型的神谕，我们详细介绍这种扩展计算理论模型。
图灵机如何成仙？——Kleene的S1-S9高阶递归理论
普通图灵机与一阶递归论，只能处理自然数；即便引入神谕图灵机，也最多把无穷序列当作外部查表，只能传入有限的自然数作为查询，无法直接描述“输入本身就是函数”这种高阶计算。
为了把可计算性拓展到无穷序列、泛函这些高阶对象，克莱尼建立了 S1‑S9 高阶递归理论。它彻底放弃纸带机器的直观图景，改用九条递归模式，用自然数索引 代表“高阶程序”，以弱相等 （两侧要么同值有定义，要么同时发散无定义）的等式展开，定义高阶部分递归泛函。其中 为任意有限类型神谕， 是由 构成的高阶输入元组。
S1‑S8 是8条规则的定义，负责实现高阶版本的原始递归，完成后继、投影、复合、参数置换、哑元添加、高阶原始递归等基础操作（参照一般的递归函数论），但仅靠 S1‑S8 的子系统能力十分有限：既不能调用高阶神谕，也不具备通用递归的自引用不动点能力。整个体系真正的力量来源于 S9 神谕调用模式：
这里，, 是程序索引（自然数），Kleene 把多个自然数编码成一个自然数： 是配对编码函数。第一个数字是9就代表：这个索引执行 S9 神谕调用；记录参数的类型信息。
是内嵌的事先定义好的 “子程序”的索引（编码）。
是递归函数论中的特有记号，定义了一个以为变元的函数，其中， 是 lambda 抽象，构造一个函数对象（高阶实参）：给定参数，这个函数的输出等于子计算。
为以为索引，以为神谕的“子程序”。
, 把刚才动态构造出来的函数 ，作为实参传给神谕黑盒；直接返回一个自然数。
这一条模式一身承担两项核心任务：第一，它统一实现全部有限类型神谕的调用，计算内部通过子计算 动态构造出需要传给神谕的高阶实参；尤为关键的是，生成实参的子计算内部还可以再次调用神谕 ，实参可以依赖神谕自身，这是普通纸带图灵机无论如何都做不到的。第二，S9 本身并不提供不动点能力；S1‑S9 体系下的高阶版本第二递归定理仍然需要单独证明。
S9模式直观例子
我们使用前面定义的Type‑2神谕 ： 接收一条无穷序列 ，一次性全局判断序列中是否存在某位置输出0。
S9模式代入 ：
简单示例（无嵌套调用神谕）
取子索引 ，其行为 。
由此构造无穷序列：
序列在 处取值为0。把 整体交给神谕 ，得到 ，于是 。
在这个简单场景，仅仅生成实参的子程序不调用神谕，启发式的索引编码假想机器勉强可以模拟。
S9独有的闭环示例（纸带机器无法模拟）
令子索引 的子计算 在求值过程中会再次调用神谕 。
此时高阶实参序列
序列每一点的取值，都依赖正在被调用的同一个神谕 。
S1‑S9等式语义天然支持：子计算写法 直接共享神谕 。
第三条路径：谓词与量词范围的扩充
下面讨论第三条升仙路径。这条路径有点剑走偏锋的意思，它不是从我们熟悉的图灵机、递归函数等概念入手，而是另辟蹊径，从谓词公式入手，不断升级。这条路径的好处是：概念简单清晰，而且有统一的符号，即，升级就体现为的增加。
基础概念回顾
先复习一些数理逻辑中的基本概念。
命题：可以判断真假的陈述语句，例如所有的“2是一个自然数”。
谓词：带有空位的命题模板，填入具体对象之后，就得到一个可真可假的命题。通俗地说，谓词相当于一个函数，并且函数值只能取真假二值。例如就是一个谓词，代表”是一个自然数“，其中就是自由变元。当取了具体的数字，例如，则谓词也就有了具体的真假值，即。
集合：借助谓词可以定义集合：把所有“代入谓词之后命题为真”的对象收集到一起，就构成一个集合。例如，谓词”\text{是一个自然数}“就定义了集合：，再如： 就定义了一个集合，这是由谓词定义的集合，而本身是图灵停机问题的神谕。可以称为图灵机的停机集合。
量词：谓词内部可以使用量词，包括全称量词 （对所有）和存在量词（存在）。量词写在谓词前面，用来遍历某一类对象。例如，“”就是一个包含了全称量词的谓词，表示的意思是：“所有的x都是偶数”；而“”就是一个包含了存在量词的谓词，表示的意思是：“存在一个x是偶数”。
算术谱系（Arithmetric Set）
在前面的讨论中，量词一般只用来遍历自然数：，变量 的取值范围都在 之内。依靠这类只量化自然数的谓词，我们得到全部算术集合，也就是算术谱系 。
这里，定义为所有形如的谓词的集合。这里存在量词和全称量词会交替出现，其中交替的次数为，并且第一个量词为存在量词。
类似的，定义为所有形如的谓词的集合。这里存在量词和全称量词会交替出现，其中交替的次数为，并且第一个量词为全称量词。
一种特殊的情况是，此时
解析谱系
想要继续向上拓展可定义的集合，一条思路就是升级量词的量化范围：不再仅仅允许量词遍历自然数，还允许量词遍历自然数之上的函数对象（Type‑1 对象，即 的函数）。
当谓词中出现了对函数的量词，我们就走出了算术谱系，从而进入解析谱系 。 其中上标1代表量词的取值对象是Type-1对象。
：包含一个存在量词的谓词所定义的集合，且取值范围为Type-1类型对象，即自然数上的所有函数集合；
：包含一个全称量词的谓词所定义的集合，且取值范围为Type-1类型对象，即自然数上的所有函数集合。
，即上述两集合的交集，这就是超算术集合 。
这条路径没有引入新的机器模型，也没有引入超限迭代；仅仅通过改变谓词里量词遍历的对象，就刻画了一类超算术集合。
算术谱系与超算术谱系的关系
我们还可以从另一个角度定义算术集和超算术集：
所谓算术集，是指这样一种自然数的子集，它能够被图灵归约到某个图灵跳集合中，其中是一个有限的自然数。
我们可以把所有这些自然数的子集合并起来（注意并不是简单取无穷多图灵跳的并集），得到一个自然数的子集，它的数学定义为：
这里的只是一种符号，其中为超限序数。也就是说，这个是一个自然数的集合，它是所有以和阶图灵跳中的元素组成的数对再进行编码而成的自然数。可以证明，构成了一个超算术集。而我们（Kleene）定义：所有可以被图灵归约到某个 的自然数集合构成的类为超算术集，即。
可以证明，算术集超算术集。
我们可以利用反证法：
假设 是算术集，那么，根据算术集的定义，必然存在某个固定的有限自然数，使得。也就是说，配备神谕 的神谕图灵机，可以判定任意元素是否属于。
然后，根据 的定义，我们可以直接得到：对任意有限自然数，有，这是因为：要判断是否属于第层 ，只需要把和层号配成，然后询问 的神谕： 是否属于集合？返回的结果就是答案。整个过程只需要一次配对和一次神谕查询，显然是图灵可计算的。
其次，取，代入上面的结论，得到。
最后，结合我们的假设，根据图灵归约的传递性，可以推出，而这是与图灵跳的基本性质相矛盾的。
因此我们的初始假设不成立：不存在任何有限的 n 使得 ，即 不是算术集。
由此可见，虽然是由所有的图灵跳合并而成的一个自然数集合，但是它却比任何一个图灵跳更高阶层的集合。
更一般的情况
类似地，我们可以引入符号：
对于一般的和，
控制“量词跑哪一类对象”：只跑自然数；可以跑函数；跑高阶泛函，即Type-m对象。
控制“同一类型内部量词交替多少次”：连续相同量词算作一个块。
下面这张表总结了一般情况下的谱系名称：
值得注意的是：
只有 的 对应超算术集合 。
只要 ，或者 但 ，Kleene三等价就不再成立（见下一小节）。
只要 ，谱系称为解析谱系。
当 ， （算术谱系）全部包含在 内部；
继续向上走到 ，就彻底离开超算术集合的范围。
通俗比喻：谱系就像一套描述语言。算术谱系是只允许谈论自然数的语言；解析谱系允许谈论无穷函数。超算术集合 ，就是在这套二阶语言里，既能用“存在某函数……”描述，又能用“对所有函数……”描述的那一部分自然数集合。语言变强了，但只有两边都能写出来的，才是超算术集合。
这条路径没有引入新的机器模型，也没有引入超限迭代；仅仅通过改变谓词里量词遍历的对象，就刻画了同一类超算术集合。这正是Kleene三条等价刻画中的逻辑‑可定义性视角。
三条不同“升仙”路径的对比
到这里我们给出了三套完全不同的“升仙using”，用来突破普通图灵计算模式，接下来就让我们把这三条路径放到一起比较异同。
路线一：序数迭代图灵跳：同一类型内部，把迭代推向超限
序数给我们的道路是：对象始终停留在Type‑0（自然数集合），不引入更高类型对象，但是把图灵跳的迭代步数拓展到超限序数。，所有这些 依然都是自然数集合，全部属于Type‑1对象；只是迭代的步数标签变成了序数 。
核心：对象类型不变，计算能力提升来源于允许做无穷多次的图灵跳迭代。
路线二：Type‑k对象升级：抬高神谕的对象类型
而第二套做法，通过引入了Type‑k对象与Kleene S1‑S9高阶递归，我们改变了神谕可以接收的数据的类型。
Type‑1神谕：输入自然数，输出自然数（自然数集合/无穷序列）；
Type‑2神谕（例如 ）：输入一整条Type‑1无穷序列，输出自然数；
Type‑3神谕（Superjump）：输入Type‑2泛函，输出自然数；
以此向上，Type‑k神谕接收Type‑的对象作为实参。
核心：计算能力的提升来源于神谕可以处理更高类型的对象，这里迭代的不是“图灵跳的次数”，而是输入输出对象的类型层级。同时，抛弃了图灵机模型，引入S1-S9高阶递归，特别是S-9直接以递归的方式定义高阶递归函数。
路线三：谓词与量词范围的扩充
第三条路径不改动计算模型，也不引入超限迭代，而是改变谓词中量词所能遍历的对象范围。算术谱系 的量词仅能遍历自然数（Type‑0 对象）；当谓词允许量词遍历 Type‑1 函数对象，就从算术谱系进入到了解析谱系 。我们依旧研究自然数的子集，集合本身仍是 Type‑1 对象；只是定义集合所用的逻辑谓词，量词的取值范围被拓宽。 使用存在函数量词， 使用全称函数量词，二者的交集 恰好刻画超算术集合。
核心：对象与机器本身不变，计算 / 定义能力的提升来源于量词可以量化更高类型的对象，这里迭代的不是图灵跳的次数，也不是输入输出的数据类型，而是逻辑公式里量词的对象层级。
三条“升仙路径”对照总结
以上三条路径，从完全不同的出发点向外拓展可计算概念：
序数迭代路径，站在集合构造的角度，依靠超限递归，用可计算序数作为迭代指标生成集合；
高阶类型路径，站在计算模型的角度，升级计算能够处理的对象类型，引入高阶泛函作为神谕；
谓词‑量词路径，站在逻辑可定义性的角度，通过提升谓词量词的遍历对象，得到更强的可定义集合。
三条路径底层都不改动自然数集合 ，研究对象始终是自然数的子集。虽然思路完全独立，但Kleene证明了三者之间存在深刻的等价关系。
三者的联系与关键区别
对象种类不同
序数迭代图灵跳生成的全部都是由 Type‑1对象刻画的自然数集合（以Type-1泛函为特征函数刻画的自然数集合）；
Type‑k（）神谕本身根本不是自然数集合，是更高阶的泛函；
量词扩充的路径则始终只研究 Type‑1对象刻画的自然数集合，只是用来定义集合的逻辑谓词可以遍历更高类型的对象，集合本身不变成高阶对象。
能力可以互相模拟，但不是天然等价
可以证明，带上Type‑2神谕 的S1‑S9高阶递归，可以模拟所有 的序数迭代图灵跳 。也就是说，借助高阶对象，我们不用直接写超限递归，就能得到全部这些Type‑1对象刻画的自然数集合。
反过来，仅仅依靠Type‑1对象刻画的集合的超限迭代 （），无法构造、无法模拟Type‑2泛函 本身。是Type‑2对象，不在Type‑1的世界里面。
逻辑‑量词路径不产生任何新对象，它只描述自然数子集；Kleene 三等价定理告诉我们：三类完全不同的手段，在刻画自然数子集这一层面上互相等价：
凡是可以由 的超限图灵跳得到的集合，恰好就是‑可计算的集合，也恰好就是可定义的集合，也就是超算术集合 。
注意等价的边界：等价只针对被输出 / 被刻画的自然数集合；高阶泛函本身、超限序数本身，三者并不是同一类东西。
三条路线继续向上延伸
Type‑k方向：继续提升对象类型，Type‑3 Superjump，它会对应一个新的临界序数 ，比 更大；
序数迭代方向：始终停留在Type‑1，上限就是 。
量词扩充方向：继续提高解析谱系的层级，走到，此时不再单纯对应以内的超限图灵跳。
通俗比喻：
Type‑k 升级，相当于你拿到一台机器，不断升级它的接口，让它可以处理越来越复杂的 “高阶数据”；
序数迭代，则是机器接口不变，只允许它把同一个操作重复无穷多次；
量词扩充路径，则是不改动机器、不新增数据，只是换一套更强的逻辑语言去描述集合。
有趣的是：把机器接口升级到 Type‑2，就足以把 Type‑1 内部所有可计算序数迭代产出的集合全部 “抓出来”；而这套集合，也刚好可以被二阶逻辑的 谓词完整刻画。但是一旦越过 的边界，三条路径就分道扬镳。
Kleene：超算术集合的三等价定理
很多神话故事都告诉我们，即使你成了神仙也并不能为所欲为，因为仙界也有仙界的规矩——“仙界法则”。同样的，在图灵机计算理论的仙界中，也存在着这样的“仙界法则”，这就是Kleene三等价定理。
等价定理的表述：对于任意自然数集合 ，下面三个命题互相等价：
序数迭代刻画：存在某个可计算序数 ，使得 图灵归约于 ；
高阶计算刻画： 在Kleene S1‑S9体系下，是 ‑可计算集合；
逻辑可定义性刻画：，即集合既能被仅包含一组存在量词的谓词定义，也能被一组仅包含全称量词的谓词定义。
满足以上任意一条的集合，就是超算术集合 。
⚠️重要边界提醒：
该等价仅仅对 这一层成立。一旦继续向上拓展：迭代指标超过 、使用比 更强的高阶泛函、进入解析谱系更高层 ，三条路径就不再保持这种简单的一一对应。
Kleene三等价定理的证明思路
我们需要证明下面三条对自然数集合 互相等价：
存在可计算序数 ，使得 ；
在Kleene S1‑S9体系下是 ‑可计算集合；
，即 同时拥有 与 的二阶算术定义。
证明采用循环推导 。
：超算术集合属于
对任意可计算序数 ，利用可计算序数记号系统，可以用函数量词去遍历全部可能的超限构造序列。
“”既可以写成“存在某条构造函数，使得 出现在该构造中”（即，这就是中的谓词公式的形式）；
又可以写成“对所有合法的构造函数，若它是 的构造，则 在其中”（即，这就是中的谓词公式的形式）。
因此 。图灵归约可以用算术描述图灵机行为，保持 ，故所有满足(1)的集合都属于 。
：每个 集合是 ‑可计算
的集合可写成 ，其中 是算术公式。
Kleene的Type‑2泛函 的核心能力，就是判定形如 的语句是否成立（ 为算术谓词）。
在S1‑S9高阶递归体系中，算术谓词本身是可计算的；借助 ，我们就可以实现对函数的存在/全称量词，从而计算出 集合的特征函数。
：‑可计算的自然数集合是超算术集合
S1‑S9中带 的每一个计算对应一棵良基计算树（简单理解就是：不存在无穷向下路径的计算树），每一次调用 对应一层子问题。
可以将计算树的高度映射到某个可计算序数 。通过对计算高度做超限归纳，可以证明：高度为 的 ‑计算的输出，能够被 图灵模拟。
⚠️关键提醒：该等价仅仅针对输出的自然数子集。 本身是Type‑2泛函，不是自然数集合，它不能被 构造出来。只是当我们把使用 的计算限制在输出自然数集合时，产出的集合族恰好就是超算术集合。
循环证毕，三者等价。
总结
总结
这篇图灵机升仙记用一种比喻的方式介绍了高阶递归理论——对计算理论、数理逻辑和递归函数理论的高阶推广。由于这类推广大多没有实际的计算模型对应，而很多介绍相关内容的书籍和文章往往又写得过于数学化，晦涩难懂，因此非常难于被像我这样的跨学科初学者学习掌握。如果把这些理论家们通过理性思维构造的无穷世界看作仙界，把有限的图灵机计算过程不断利用神谕而升级的过程看作是升仙，我发现抽象的理论就不再难以理解，于是就构思了这篇文章。但由于作者本人尚属初学者，水平有限，一些错误在所难免，望读者见谅。衷心希望，读到它的读者能够燃起对计算理论、递归函数论等相关内容的兴趣，能够进一步学习。
附录：读者“升仙”路径
附录：读者“升仙”路径
读完本文，如果希望继续向上 “升级”，进一步吃透图灵机、可计算性与高阶递归论的相关内容，可以沿着下面的文献继续进阶。下面按从入门到高阶的梯度列出参考资料，读者可以按需选取，顺着这条路径继续深挖理论细节，完成自己的知识升级。
[1] Rogers H. Theory of Recursive Functions and Effective Computability [M]. McGraw‑Hill, 1967.（递归论经典教材，覆盖基础可计算理论）
[2] Odifreddi P G. Classical Recursion Theory (Volume Ⅰ,Ⅱ)[M]. North‑Holland, 1989,1999.（经典递归论大部头，图灵度基础核心参考书）
[3] Sacks G E. Higher Recursion Theory [M]. Springer‑Verlag, 1990.（高阶递归论标准专著，本文涉及高阶部分的主要进阶读物）
[4] 郝兆宽，杨睿之，杨跃。递归论 [M]. 复旦大学出版社，2018.（中文递归论教材，适合国内读者过渡）
[5] Turing A M. On Computable Numbers, with an Application to the Entscheidungsproblem [J]. Proceedings of the London Mathematical Society, 1936, 2 (42):230‑265.（图灵机原始经典论文）
[6] Church A. An Unsolvable Problem of Elementary Number Theory [J]. American Journal of Mathematics, 1936,58 (2):345‑363.（丘奇论题原始文献）
说明：不必强行从头到尾通读全部著作，可以结合自己的问题定向翻阅章节；基础概念优先读教材，想要追溯思想源头再回看原始论文。
文章精选：
1.图灵奖得主姚期智最新演讲： AI有边界，恰恰是好事
