05A

约 9545 个字预计阅读时间 32 分钟

之前我们花了很多时间讨论各种计算模型，但是这些模型似乎都不符合对计算机的普遍认知。有限自动机似乎受制于失忆的可能，下推自动机的记忆则只有一个受限的栈。唯一引人遐思的是 Kleene 机的模型，它似乎通过代数的方式给出了一个相当广泛的可计算性定义。在这里我们要引入图灵机，计算理论历史上最经典、最引人注目的概念之一，它将成为现代计算机的一种模板，同时也会成为后续讨论的重要基石：虽然“不如” Kleene 机广泛，但是它足以成为一种形象化的模型来讨论可计算性。

当然，图灵机事实上也是相当受限的。因为高阶（higher-order，例如函数，在下一节会给出明确的定义）的对象通常被编码为实数（考虑将 \(\mathbb{N}^{\mathbb{N}}\) 的函数往实数建立一一对应，这种函数被称为类型 1 的对象，type 1 object，这种对应的一个例子是 Kohlenbach 的“帽子”，在后面介绍高阶可计算性的时候会对这些东西给出更加详尽的表达），这会导致很多不同的结果，例如 D. Normann 等人对几乎处处连续的函数的讨论。

确定性图灵机、递归可枚举语言和递归语言 Deterministic Turing Machine, Recursively Enumerable Languages & Recursive Languages¶

可以从两种方式抽象出图灵机的模型。一者，考虑以往的模型何以不充分，进而给出增添式的改进；二者，考虑现存的计算机如何存在，进而抽丝剥茧去除其中不重要的部分。

对于前者，引言中业已表明前述部分模型的缺陷，它们要么没有记忆，要么记忆受限。因此，不妨以一条纸带作为记忆，构建一个可以任意读写的模型。对于后者，现代的计算机无不具备内存，甚至具备内存层次结构，这在计算中是非常有意义的。因此，纸带不过是一种对复杂的内存系统的抽象。无论如何，我们都可以得到类似如下的定义：

定义

一台图灵机（Turing machine） \(M\) 是一个五元组 \((K, \Sigma, \delta, s, H)\)：

\(K\) 是一个有限的状态集；
\(\Sigma\) 是一个字母表，这里要求它包含左端记号（left end symbol） \(\triangleright\) 和空格符（blank symbol） \(\sqcup\)；
\(s \in K\) 为初始状态；
\(H \subseteq K\) 为停机状态集；
\(\delta\) 为状态转移函数 \((K - H) \times \Sigma \to K \times (\Sigma \cup \{\leftarrow, \rightarrow\})\)，需做如下限制：
1. \(\forall q \in K - H, \exists p, \delta(q, \triangleright) = (p, \rightarrow)\) （左端永远右移）
2. \(\forall q \in K - H, \forall a, b \in \Sigma, \delta(q, a) \neq (p, \triangleright)\) （不会写左端记号）

由于 \(\delta\) 是一个一一映射，像对前面的各种机器一样，也称之为确定性的图灵机（deterministic Turing machine, DTM）。

这样的定义看起来非常抽象，但用纸带的方式来解释它并不困难。既然有纸带用作记忆，那么显然就有以下几种可能：

读写头在纸带上左移；
读写头在纸带上右移；
读写头向纸带上写；

之所以读不重要，是因为操作的过程中我们都默认读写头是可以读的，也就是说，它永远知道它读写头下面的符号是什么。因此，状态转移函数中添加的 \(\{\leftarrow, \rightarrow\}\) 就表征了读写的过程；\(\triangleleft\) 表征纸带的最左端，\(\sqcup\) 则表示纸带在这个位置是一片空白。两个要求也不难理解，一方面，图灵机不应该把左端符号写坏掉；另一方面，图灵机也不能随便将某个位置标记为纸带的左端。

接下来我们就可以定义图灵机的格局（configuration），它指的就是图灵机在某时刻所处的状态。它是下面这个集合的成员：

\[ K \times \triangleright(\Sigma - \{\triangleright\})^\ast \times ((\Sigma - \{\triangleright\})^\ast(\Sigma - \{\triangleright, \sqcup\}) \cup \{e\}) \]

看起来很吓人？实际上可以把它拆成三部分理解：

它当前处于哪个状态；
它从最左端往后到读写头位置（包含读写头）的字符串内容；
它从读写头往后的字符串，直到全是空格为止；

在实际情形中，我们通常使用下划线来表达读写头的位置。例如：

\[ (q, \triangleright a \sqcup b, a \sqcup \sqcup b) \equiv (q, \triangleright a \sqcup \underline b a \sqcup \sqcup b) \]

因此，形象地定义它的一步操作就是：

定义

称图灵机 \(M\) 能从格局 \((q_1, \triangleright w_1 \underline a_1 u_1)\) 转变为 \((q_2, \triangleright w_2\underline a_2 u_2)\)，若它满足以下几个条件：

（写入）\(\delta(q_1, a_1) = (q_2, a_2), w_2 = w_1, u_2 = u_1\)；
（左移）\(\delta(q_1, a_1) = (q_2, \leftarrow), w_1 = w_2a_2, u_2 = a_1u_1 \text{\;or\;} e \text{\;if\;} a_1 = \sqcup, u_1 = e\)
（右移）\(\delta(q_1, a_1) = (q_2, \leftarrow), w_2 = w_1a_1, u_1 = a_2u_2 \text{\;or\;} e \text{\;if\;} a_2 = \sqcup, u_2 = e\)

记作 \((q_1, \triangleright w_1 \underline a_1 u_1) \vdash_M (q_2, \triangleright w_2\underline a_2 u_2)\)。

如果它可以在有限步（包括 0 步）内完成这样的转换，那么将其记为 \((q_1, \triangleright w_1 \underline a_1 u_1) \vdash_M^\ast (q_2, \triangleright w_2\underline a_2 u_2)\)

如果图灵机能够从起始状态和某个格局到达 \(H\) 中的状态，就称这个图灵机停机（halts）。利用这个概念，它就能做出一个 0/1 判断，这就等价于计算一个示性函数。因此，就有了半判定的概念：

定义

称一个图灵机 \(M\) 半判定（semidecide）一个语言 \(L\) 如果：

（充分性） \(\forall w \in L, \exists h \in H, (s, \triangleright \underline \sqcup w) \vdash_M^\ast (h, \cdots)\)；
（必要性） \(\forall w \not \in L, \lnot (\exists h \in H, (s, \triangleright \underline \sqcup w) \vdash_M^\ast (h, \cdots))\)；

记 \(L(M) = L\)。

这里的定义看起来稍微有点冗长。但是考虑到以后复杂性理论讨论的需要，这样的麻烦也是必须的。充分性和必要性在概率复杂度类相关的讨论中将成为标准定义之一；事实上，它和 PCP 定理息息相关。

这样事实上就给出了递归可枚举语言的定义：

定义

称一个语言是递归可枚举的（recursively enumerable），如果存在一个图灵机半判定这个语言。

但是，这样的限制似乎不够强：判断一台图灵机停不停机会耗费无限长的时间，哪怕你等了充分长的时间，它也可能明天就停机，或者永远也不再停机。因此，如果要在有限时间内知道一个字符串是否属于某个语言，那么就不得不给出一个必然停机的结果。鉴于停机状态集合是一个集合，我们不妨假定它为 \(\{y, n\}\)，接下来同样做出如下定义：

定义

称一个图灵机 \(M\) 判定（decide）一个语言 \(L\)，如果：

（充分性） \(\forall w \in L, \exists h \in H, (s, \triangleright \underline \sqcup w) \vdash_M^\ast (y, \cdots)\)；
（必要性） \(\forall w \not \in L, \exists h \in H, (s, \triangleright \underline \sqcup w) \vdash_M^\ast (n, \cdots)\)；

称一个语言是递归的（recursive），如果存在一个图灵机判定这个语言。

接下来的结果看上去是显然的：

命题

递归语言一定是递归可枚举语言。

证明

只需考虑，如何使得这两种状态中的一种无限循环。对于所有到达状态 \(n\) 的图灵机，使得它的状态转移函数为不断空转，即

\[ \delta(n, \cdots) = (n, \cdots) \]

这样就自然使得新的图灵机就是一个半判定此语言的图灵机。

下面这个命题也给出了一个对递归语言的刻画，其证明不难不妨留给读者。但是，这个命题在构造数学（constructive mathematics）中并不是逻辑上合法的，称为 Markov 原理，这些问题是逻辑上重要的，然而本文不会予以展开。

命题

如果 \(L\) 和 \(\bar L\) 都是递归可枚举的，那么 \(L\) 是递归的。

下一个问题也就很自然了：递归可枚举语言和递归语言之间是否夹着什么东西？递归可枚举语言和全体语言之间是否也夹着什么东西？我们很快就会给出相应的构造，但是在这里，对于后者给出一个肯定的回答并不困难。

命题

存在一个语言不能被图灵机半判定。

证明

注意到，定义图灵机的五元组当中每一个集合都是有限的，因此，所有图灵机构成的集合是可数的；而所有语言的集合是不可数的，这可以由对角线法（diagonalization）轻松地论证：

假设存在一个从自然数到语言的一一映射 \(L\)，则考虑 \(\{L(i)\} = 2^{\Sigma^\ast}\)。接下来试构造一个语言使得它不在 \(\{L(i)\}\) 之中。由于 \(\Sigma^\ast\) 是可数的，将每个字符串赋予一函数 \(f: \mathbb N \to \Sigma^\ast\)。考虑由以下方式定义的语言：

\[ L^\prime = \{s_i: s_i \not \in L(i)\} \]

因为对于任意 \(L \in \{L(i)\}\)，都存在 \(s_i \in L^\prime\) 使得 \(s \not \in L\)，\(L^\prime \not \in \{L(i)\}\)。这与上面的假设矛盾。

事实上，这个结论可以看成 Lawvere 不动点定理的一个推论，在后面关于结构性不动点的一节中会重点说明。从集合论的角度看，这也是 Cantor 定理的必然推论。

这个论证同时表明，若在所有语言的集合上赋予恰当的测度，则递归可枚举语言事实上是零测的：随便构造一个语言它是递归可枚举的概率就是 \(0\)。直观的说，图灵机面对所有语言来说渺如沧海一粟。但在下面，我们又会看到，对于人类的智识活动而言，图灵机竟又是一道不可逾越的鸿沟，多少还是有些引人深思的意味。

递归可枚举语言和递归语言的闭包性质对于读者来说应当不难自己证明：

递归可枚举语言对并、交、衔接和星封闭，对差不封闭；
递归语言对并、交、差、衔接和星都封闭。

最后，不妨给出图灵机计算某个函数的定义。

定义

称一个函数 \(f: \mathbb \Sigma^\ast \to \mathbb \Sigma^\ast\) 是可计算的（computable，或递归的，recursive），如果存在一个图灵机 \(M\)，使得：

\[ \exists h \in H, (s, \triangleright \underline \sqcup w) \vdash_M^\ast (h, \triangleright \underline \sqcup f(w)) \]

不难发现它和判定一个语言殊途同归。判定一个语言附加一步写入 0/1 和填掉其它非空字符的操作就是一个计算示性函数的过程，当然，在这里这样的表述尚且不够严谨，需要用下一节的手法来让它包装成一个好的叙述。

一些例子，其与算法的等价性 Examples & Equivalence to Algorithm¶

为了理解图灵机，不妨考虑一些例子。这些例子在标准教材中也应当相当充分，但在这里，因为笔者希望读者更多着眼于理论框架而非细枝末节，故只会给出一些具备理论意义的例子以备讨论。

三种很自然的图灵机对应于上节界定的三种操作：写、左移和右移。构造其对应的图灵机应当不难，只是无论在何处都执行一步此操作然后停机。
分支：根据读到的内容决定下一步运行某个图灵机的操作。这应当也不难，和有限状态机旨趣相同。这样也就建立了循环的概念。

因此，用图示表示图灵机变得可能了：分支和循环被建立，基本操作和基本操作的级联（cascade）也毫无困难。因此，可以直接宣称，描述一种算法事实上和描述图灵机别无二致，只是算法的每一步都应当有一个对应的图灵机来完成。这样的陈述使得我们对图灵机的描述更加简单了：输入、分支和执行构成了整个描述的所有基本操作，它们等价于编程语言的读取、判断（循环）和跳转过程。下面我们都将用形似自然语言的伪代码来描述图灵机。

（失败的）模型推广 (A Failed Attempt to) Extend the Model¶

在构造反例之前，我们将首先考察更多更丰富的图灵机模型。这些模型往往看上去比原来的机器更加强大，但它们并不能给出更强的结果。这事实上说明了图灵机模型的强大之处：似乎它就是一个计算能力的上界。

这一节中的证明异常多而繁琐，在标准教材中通常也不吝笔墨。但是这不是标准教材，且笔者认为这些模型事实上难以起到什么重要意义，因此在此只给出简单的思想方法，若读者有兴趣，自可参考标准教材，也可自行丰满其内容。

第一种推广是随机存取的图灵机，将左移、右移操作替换成移至某个位置。看上去这似乎使得它变强了，但细想之下就会发觉，这只是“加速”了它的运算过程。任意有限步移动都可以靠对状态机的简单修改表征，因此它并不能提升图灵机的计算能力。

第二、三、四种推广分别是两端无限长、多带图灵机和二维平面上的图灵机。细想就会发现，无论怎么推广，纸带的长度还是可数格，因此，编号的想法就已经足够了。当然，对于两端无限长和多带的情形，也可以通过在同一格填充多个符号来处理，这就等价于编号的思路。

第五种推广是多头图灵机。多个读写头事实上只要能记下多个头的位置就可以模拟。通过对读写头的位置加下划线标记，补充字母表即可。

最后一种推广，非确定性图灵机是值得仔细考察的一种，它在后面讨论复杂度理论时会发挥几乎不可替代的作用。

定义

一台非确定性图灵机（non-deterministic Turing machine，NTM）是一个五元组 \((K, \Sigma, \Delta, s, H)\)，其中其它四项都与 DTM 相同，但是 \(\Delta\) 是以下集合的有限子集：

\[ ((K - H) \times \Sigma) \times (K \times (\Sigma \cup \{\leftarrow, \rightarrow\})) \]

容易看出，这个形态就是和 NFA 一致的。格局的定义是和 DTM 一致的。而我们定义它半判定一种语言的方式和 DTM 也是完全一致的。注意，这样我们声明的是，存在某个分支停机，而不是任意分支停机。

当然，判定一种语言的定义方式也是一样的。也就是说，任意属于 \(L\) 的字串，存在一个分支接受它；任何不属于 \(L\) 的字串，任何分支都不接受它。

命题

任何一个 NTM 都可以被一个 DTM 模拟。

证明

直观地，可以把一个 NTM 看作一个树状结构，而 DTM 是一个链式的运行过程。因此需要考虑的就是一个树的遍历任务。当然，在 DFS 和 BFS 需要做出一种选择：DFS 是不行的，因为它搜索到一个无穷的分支就会无限搜索；BFS 则可以搜索到一个有穷的分支则停止搜索。因而我们考虑 BFS。

为了方便起见，下面考虑三带图灵机，这种形式会更有利于下面的表述。第一条纸带用来存储输入，第二条纸带用来模拟 NTM 的运行，第三条纸带用来记录遍历到了哪个位置。每一次模拟几步运行，然后停下，将第二条纸带用第一条纸带来覆写掉，再改写第三条纸带的内容，重新模拟。

NTM 的意涵事实上是十分丰富的，在后面会介绍的 \(\sharp P\) 函数，以及关于几个经典概率复杂度类的证明都会利用 NTM 实现。

在这些尝试之后，丘奇-图灵论题（Church-Turing thesis）的导出也就显得有些理所应当了：

Church-Turing 论题

图灵机表征最强的可计算性，即任何问题如果可被物理系统计算，则一定能被图灵机计算。

哪怕到了今天，这个论题也没有被打破，反而延伸出了新的意蕴。例如，在经典物理的层面，Gandy 给出了一个合理假设下的证明。P. Arrighi 等人则将其推广到了量子层面，将理论物理的对称性充分地应用于可计算性层面，这些话题在物理相关的杂谈一节中将会得到尽可能充分的展现。

停机问题 Halting Problem¶

接下来需要做的是构造递归可枚举而非递归的语言以及非递归可枚举的语言。核心的想法就是停机问题：

\[ H = \{"M""w": M \text{\;is\;a\;TM\;that\;halts\;on\;} w\} \]

其中 \("M"\) 指的是图灵机 \(M\) 的编码：毕竟图灵机是可数的，它当然也可以被编码出来。

命题

\(H\) 是递归可枚举的。

证明

只需要使用一个通用图灵机来模拟这个图灵机，直接在 \(w\) 上运行 \(M\)，如果它停机，那这个图灵机也停机。这个语言就被这个通用图灵机所半判定了。

下一步欲证它不是递归的。为了证明这一点，需要用到另一个语言作为中介，它事实上就是这个语言的对角线化：

\[ H_d = \{"M": M \text{\;is\;a\;TM\;that\;does\;not\;halt\;on\;} "M"\} \]

引理

\(H_d\) 不是递归可枚举的。

证明

使用反证法。如果 \(H_d\) 是递归可枚举的，那么存在图灵机 \(D\) 半判定 \(H_d\)，也就是说，如果 \("M" \in H_d\)，则 \(D\) 停机，反之不停机。接下来考虑 \("D"\) 与 \(H_d\) 的关系。根据 \(H_d\) 的定义，如果 \(D\) 在 \("D"\) 上不停机，则它属于 \(H_d\)，因此根据半判定的定义，\(D\) 应该在 \("D"\) 上停机，矛盾。

目光如炬的读者当不难发现这个证明与对角线化论证的旨趣大抵相同。通过取对角线的方法引出矛盾自 Cantor 以来就成为了一种几乎固定的方法论。至于如何形式化这套方法论以及如何明确它的应用，在结构性不动点定理一节将给出足够严格的论述，在复杂性理论中，这会成为不可或缺的一套方法。

上面的引理为下面的命题做好了准备：

命题

\(H\) 不是递归的。

证明

注意到，因为 \(H_d\) 不是递归可枚举的，所以它一定不是递归的。因此，下面将使用这样的命题导出矛盾：如果 \(H\) 是递归的，那么 \(H_d\) 就是递归的。

这个结果几乎是显而易见的。如果考虑 \(H\) 是递归的，那么存在图灵机 \(M_H\) 判定这种语言。给 \(M_H\) 以输入 \("M""M"\) 就能判定 \(H_d\)。因此，若 \(H\) 是递归的，那么 \(H_d\) 也是递归的，前文业已表明 \(H_d\) 不是递归的，这就表明 \(H\) 不是递归的。

复盘一下这一节的内容，虽然稍微有点绕，但笔者希望这个构造的精妙之处在这里能够得以体现。当然，在后面的几章中，更重要的事情是表明这个构造不是神来之笔，它本身有相当深的范畴论意涵和更加合适的解读。

首先，我们证明了 \(H\) 是递归可枚举的，然后，为了表明它不可递归，构造了一种不是递归可枚举的语言 \(H_d\)，然后证明了如果 \(H\) 递归则 \(H_d\) 递归，利用它的逆否命题做演绎，证明了 \(H\) 不是递归的。

下面请将目光聚焦到后半部分，在表明 \(H\) 不是递归的时候，我们事实上用到了归约（reduction）的思想。如果解决 A 问题相当于解决 B 问题，那么解决 B 问题事实上比解决 A 问题更难——乍一看可能有点反直觉，因为解决 A 问题需要多经历一次转化。但是注意，这不是解决 A 问题的唯一方法。当然它可以相当于解决 C 问题，解决 D 问题，但是如果你能够解决 B 问题，它就迎刃而解了。因此，A 问题事实上不难于解决 B 问题（而不是比 B 问题简单）。这种想法就是下一节讨论的主题，事实上也是计算理论发展过程中的一大主要手法。

归约 Reduction¶

为了形式化地解释上面的问题，不妨给出以下定义：

定义

一个从语言 \(A\) 到语言 \(B\) 的 Turing 归约（Turing reduction，在常规语境中省称规约）是一个可计算函数 \(f: \Sigma_A^\ast \to \Sigma_B^\ast\) 使得：

\[ \forall x \in \Sigma_A^\ast, x \in A \iff f(x) \in B \]

记作 \(A \leqslant_T B\)

这个记号事实上就暗示了上一节末费尽心思讲明的问题：\(A\) 不会比 \(B\) 更难计算。因此，可以说归约确定了一个问题难度的界。现在提及一下等价定义或许是合适的：给定解决 \(B\) 问题的谕示机（oracle），即现在任何问题 \(B\) 的求解都可以在一步内完成，则存在一个带此谕示机的图灵机能够求解 \(A\) 问题。关于谕示机的问题，在后面会有专文述及。

不难发现：

命题

\(A \leqslant_T B \Rightarrow \bar A \leqslant_T \bar B\)

当然，有不等号就能有等号：

定义

\[ A =_T B \iff A \leqslant_T B \wedge B \leqslant_T A \]

很容易发现这是一个等价关系。基于这一点继续给出 Turing 度和 Turing 跳跃的定义：

定义

由上面等价关系对 \(2^{\Sigma^\ast}\) 划分得到的等价类称为 Turing 度（Turing degree）；Turing 度 A 中的停机问题的图灵度为 A^\prime，称为 A 的 Turing 跳跃（Turing jump）。

现在引入这些定义或许过于抽象，在后面介绍了谕示机之后，我们将可以给它更加容易理解的描述，Kleene 和 Post 等人对这些概念做了相当丰富的研究，很多结果则在上世纪末刚刚建立。当然，这是应当另开专文讨论的内容。

接下来不妨看几个例子来更好地理解这个概念。总得来说，除了 \(H\) 和 \(H_d\) 的构造因为不动点的特殊性而变得如同神来之笔，其它关于非递归可枚举、非递归的证明几乎都需要把 \(H\) 或 \(H_d\) 归约到待考察的问题。例如，我们将表明下面这个语言不是递归的：

\[ H_e = \{"M", M \text{\;is\;a\;TM\;that\;halts\;on\;} e\} \]

证明

再次提醒需要把 \(H\) 规约到 \(A\)。等价定义或许更好理解：如果给出了一个解决 \(A\) 的图灵机，那么就有一个解决 \(H\) 的图灵机。考虑构造一个图灵机，它不论输入如何，都会在 \(w\) 上运行 \(M\)。那么解决 \(A\) 的图灵机将会表明这个图灵机是否会在 \(e\) 上停机，那就是表明 \(M\) 是否会在 \(w\) 上停机。

这个构造是相当常见的，准此思想，同样可以证明以下语言都不是递归的：

\[\begin{array}{l} H_{\text{some}} &= \{"M", M \text{\;is\;a\;TM\;that\;halts\;on\;some\;input}\}\\ H_{\text{all}} &= \{"M", M \text{\;is\;a\;TM\;that\;halts\;on\;every\;input}\}\\ \end{array}\]

下一个结果也是重要的：

命题

\(\{"M_1""M_2": M_1, M_2 \text{\;are\;TMs\;and\;}L(M_1) = L(M_2)\}\) 不是递归的。

证明

这次我们做从 \(H_{\text{all}}\) 到它的规约。不妨构造图灵机 \(M^\ast\)，它不管输入为何值都直接停机。因此，如果我们可以求解此语言，那么只要输入 \("M""M^\ast"\) 就可以获得一个 \(M\) 是否属于 \(H_\text{all}\) 的结果。

最后再来一个命题：

命题

\(R_{\text{TM}} = \{"M": "M" \text{\;is\;a\;TM\;and\;} L(M) \text{\;is\;regular}\}\) 不是递归的。

证明

前已声明递归语言对差封闭，因此它也对补封闭。接下来的尝试是将 \(H\) 归约到 \(\bar R_{\text{TM}}\)。为此，不妨构造这样一个图灵机，它首先在 \(w\) 上运行 \(M\)，然后在 \(v\) 上运行通用图灵机 \(U\)。如果第一步的过程可以停机，那么它半判定的语言就是 \(H\)，而 \(H\) 不是正则的；如果第一步的过程不能停机，那么它半判定的语言就是 \(\varphi\)，它是正则的。因此，对这个图灵机的编码运行 \(\bar R_{\text{TM}}\)，如果它停机了，那么 \(H\) 也就被判定了。

这样的构造与正则性其实无关。注意到，\(H\) 事实上不是上下文无关的，也不是递归的，因此类似的性质对应的图灵机也可以被证明是非递归的。更进一步地，我们可以给出 Rice 定理，以上的所有结果都是它的一个推论：

定理

形如 \(\{"M": M \text{\;is\;a\;TM\;and\;}L(M) \in L\}\) 的语言都是非递归的，若 \(L\) 为所有递归可枚举语言的集合的一个非空真子集。

证明

首先考虑 \(\varphi \not \in L\) 的情形。存在语言 \(A \in L\) 为递归可枚举的，记半判定它的图灵机为 \(M_A\)。那么构造一个对输入 \(v\)，首先在 \(w\) 上运行 \(M\)，然后在 \(v\) 上运行 \(M_A\)。这样的话，这个图灵机半判定的语言在 \(M\) 在 \(w\) 上停机时为 \(A \in L\)，它被判定这种语言的图灵机所判定，因此，判定它就相当于判定了 \(H\)。

对于 \(\varphi \in L\) 的情形，注意到 \(\varphi \not \in \bar L\)，故如上命题的构造方式即可得出结果。

直观地说，这个证明就是充分利用了 \(\varphi\) 和 \(H\) 的性质将其“压”在了空集和递归可枚举语言构成的集合之中。在更高阶的情形下，这种思想也由其用武之地。

枚举器 Enumerator¶

TODO

不受限语法 Unrestricted Grammar¶

前面已经多次引入了语法的概念，兹再次呈现不受限语法的定义：

定义

一个不受限语法（unrestricted grammar） \(G\) 是一个四元组 \((V, \Sigma, S, R)\) ，其中：

\(V\) 是一个有限集，称为符号集（set of symbols）；
\(\Sigma \subseteq V\) ，其中的元素称为终止符（terminals）；
\(S \in V - \Sigma\)，称为起始符（start symbol）；
\(R \subseteq V^\ast(V - \Sigma)V^\ast \times V^\ast\)，是一个有限集，称为生成规则，其中的元素记为 \(A \rightarrow u\)，若 \((A, u) \in R\)。

其它相关定义不再赘述。这里的重点在于以下定理：

定理

一个语言由不受限语法生成当且仅当它被一个图灵机半判定。

证明

首先表明，不受限语法生成的语言一定能被图灵机半判定。注意到，如前在 CFG 处的视角，可以将语法生成语言的过程看成一棵树生长的过程。从起始符 \(S\) 出发，逐层以 BFS 的方法遍历这棵树；或者直接用 NTM 表达这棵树即可。这里隐含的一件事是，需要说明每一步生成都可以由图灵机所完成，在算法视域下理解这点并不困难。

其次，需要对一个图灵机半判定的语言构造不受限语法。不失一般性地，假设图灵机定义五元组中 \(K \cap \Sigma = \varnothing\)，停机状态 \(H\) 为单元素集 \(\{h\}\) 且停机时的格局总是 \((h, \triangleright \underline \sqcup)\)。注意到，图灵机半判定一个语言的过程就是存在一个从 \(w\) 到 \((h, \triangleright \underline \sqcup)\) 的转换，在生成的过程中则需要将其反转：

构造语法 \(G = (V, \Sigma^\prime, S, R)\)，其中符号集 \(V = K \cup \Sigma \cup \{S, \triangleleft\}\)，新字母表 \(\Sigma^\prime = \Sigma - \{\triangleright, \sqcup\}\)，起始符 \(S\) 就是起始状态 \(S\)，接下来要构造的就是生成规则，将其分成五种情形：

\(S \rightarrow \triangleright \sqcup h \triangleright\)。它表示停机时的格局；
\(\triangleright \sqcup S \rightarrow e, \triangleleft \rightarrow e\)，是从任一起始格局到其对应字符串的转换；
写入操作：如果图灵机有 \(\delta(q, a) = (p, b), a, b \in \Sigma\)，则 \(bp \rightarrow ap\)，即向读写头处做了一次生成；
右移操作：如果图灵机有 \(\delta(q, a) = (p, \rightarrow)\)，则 \(abp \rightarrow aqb, \forall b \in \Sigma\)，这象征读写头的移位；注意，对于已经在最右端的情形，因为右端可以随意添加东西，考虑 \(a\sqcup p \triangleleft \rightarrow aq\triangleleft\)；
左移操作：如果图灵机有 \(\delta(q, a) = (p, \leftarrow)\)，则 \(pa \rightarrow aq\)，\(p\triangleright \rightarrow \sqcup q \triangleleft\)。

再次强调，这里定义的语法是倒叙的。从停机状态出发给出任意字符串，这就是图灵机计算的逆向过程，生成规则正好把图灵机的每一步操作都倒过来，就得到了可以生成与图灵机半判定的语言相同的语言的语法。

因此，很自然地声称，不受限语法生成的语言就是递归可枚举语言，这在语法和计算模型之间建立了一个相当标准的模型。这种“计算能力”的衡量将很自然地引入 Turing 等价和 Turing 完备的概念。

Turing 等价和 Turing 完备 Turing Equivalence & Turing Complete¶

TODO: 定义，逻辑电路和图灵机，为电路复杂性做铺垫

原始递归函数 Primitive Recursive Functions¶

在前面已经给出了图灵机计算一个函数的定义，那么计算数值函数的可能也是显然的：鉴于 \(\Sigma^\ast\) 的可数性，可以建立它和 \(\mathbb N\) 的一一对应，因而也就能用 \(\Sigma^\ast\) 编码 \(\mathbb N\)，甚至编码 \(\mathbb N^k\) 中的对象。这给了我们一种最低阶的函数的刻画：\(f: \mathbb N^k \rightarrow \mathbb N\)，或者 \(f: \mathbb N \rightarrow \mathbb N\)，它们从可计算性的角度上看没什么区别，为了普遍性起见，我们考虑前者，但必须记住，这两者是可以相互归约的。在本章中，我们只会讨论一些简单的情形，更加复杂和深远的理论将在可计算函数一章中单独讨论。

下面的定义很直观的来源是 Peano 公理体系：

定义

称一个函数是原始递归函数（primitive recursive function），如果它满足以下条件之一：

它是基本函数（basic functions），即以下三者之一：
1. 零函数 \(z_k(n_1, \cdots, n_k) = 0, \forall n_1, \cdots, n_k \in \mathbb N\)；
2. 投影函数 \(p_{k, j}(n_1, \cdots, n_k) = n_j, k \geqslant j\)；
3. 后继函数 \(\text{succ\;}(n) = n + 1\)；
它是原始递归函数的复合：设 \(g: \mathbb N^k \to \mathbb N, h_i: \mathbb N^t \to \mathbb N, i = 1, \cdots, k\)，它们的复合 \(f: N^t \to N\) 定义为 \((n_1, \cdots, n_t) \mapsto g(h_1(n_1, \cdots, n_t), \cdots, h_k(n_1, \cdots, n_t))\)；
它是由原始递归函数递归定义的：设 \(g: \mathbb N^k \to \mathbb N, h: \mathbb N^{k+2} \to \mathbb N\)，则由 \(g\) 和 \(h\) 递归定义的函数是一个 \(\mathbb N^{k + 1} \to \mathbb N\) 的函数：

\[ f(n_1, \cdots, n_k, t) = \begin{cases} g(n_1, \cdots, n_k), t = 0\\ h(n_1, \cdots, n_k, t, f(n_1, \cdots, n_k, t - 1)), t \geqslant 1 \end{cases} \]

当然，这样的例子非常充足，简单的情形列举如下，读者不妨自行验证之：

命题

以下函数都是原始递归函数：

\(\text{plus\;}(m, n) = m + n\)；
\(\text{mult\;}(m, n) = m \cdot n\)；
\(\text{exp\;}(m, n) = m^n\)；
\(\text{c\;}(n_1, n_2, \cdots n_k) = c\)；
\(\text{sgn\;}(n) = 1\text{\;if\;} n \geqslant 1\text{\;else\;}0\)；
\(\text{pred\;}(n) = n - 1 \text{\;if\;} n > 0 \text{\;else\;}0\)；
\(m \sim n \equiv \text{tminus}(m, n) = \max\{m - n, 0\}\)

推论

原始递归函数对和、积和上述 7 中的减法封闭。

注意上面的第五个例子。它的值为 0/1，这当然有一些特殊的意义，在逻辑那一节事实上已经论及：

定义

称一个 0/1 值的函数为一个谓词（predicate），一个谓词是原始递归的，即指这个谓词对应的函数是原始递归的。

命题

若谓词 \(p\) 是原始递归的，则 \(\lnot p\) 也是原始递归的。
若谓词 \(p, q\) 都是原始递归的，则 \(p \wedge q, p \vee q\) 也是原始递归的。
若谓词 \(p\) 是原始递归的，函数 \(f, g\) 也是原始递归的，则 \(p\dot g + \lnot p \dot h\) 也是原始递归的。

证明

只需注意到 \(\lnot p = 1 \sim p\) 即可；
注意到 \(p \wedge q = p \cdot q\)，然后用 de Morgan 律即可；
可由上述结论自然得出；

注意到，3 规定了 cases 的可能性，现在分段函数也可以更轻松地表达出来了，因此有：

命题

以下函数或谓词也是原始递归的：

\(\text{divisiblep\;}(m, n)\)；
\(\text{rem\;}(m, n) = m \% n\)；
\(\text{div\;}(m, n) = \text{floor\;}(m/n)\)；
有限个原始递归函数之和与积；
有限个原始递归谓词之合取与析取；

最后我们给出原始递归函数与图灵机计算的函数的关系：

定理

任一原始递归函数都是可计算的。

证明

只要证明基本的函数可计算，且两种操作也可计算即可。参照级联图灵机构成算法的想法应当不难。

但是，不是所有的可计算函数都是原始递归函数，为了说明这件事情，首先给出这样一个引理：

引理

存在一个可计算函数 \(f(m, n)\) 使得：

对任意原始递归函数 \(g\) 和自然数 \(n\)，存在自然数 \(m\) 令 \(f(m, n) = g(n)\)；
对于任意自然数 \(m\)，\(h(n) = f(m, n)\) 是原始递归的。

这个引理就意味着原始递归函数是可以枚举的，也就是说，原始递归函数有可数个，它们构成的集合是递归可枚举的。

证明

因为只有有限种基本函数和复合、递归两种产生新函数的手段，故可以采用遍历树的方式遍历之。

命题

如上构造的 \(f\) 不是原始递归函数。

这个命题的证明和停机问题的构造又是一致的，使用了对角线化的想法。读者在看到这里的时候应已经可以自行给出证明。

在这个夹层中，最传统的具体例子就是：

定义

定义 Ackermann-Péter 函数如下：

\[ A(i, j) = \begin{cases} j + 1, \text{if\;} i = 0\\ A(i - 1, 1), \text{if\;} i \neq 0 \wedge j = 0\\ A(i - 1, A(i, j - 1)), \text{otherwise} \end{cases} \]

但是关于这个函数的性质还需要再铺垫一些内容之后再做介绍。另有一些更加丰富的例子，如 Paris-Harrington 定理构造的结果，Sudan 函数和 Goodstein 函数，等等。

TODO: p. r. function 的增长速率，用 Ackermann 函数来刻画 p. r. function 作为 t. r. function 的子集的限度；

在强化这种构造使得它可以覆盖可计算函数之前，首先考察一些弱化情形，它们往往有一些理论上的趣味。

弱化情形 Weakened Cases¶

TODO: weak p. r. & iterative functions

强化：\(\mu\)-递归函数 Strengthening: \(\mu\)-recursive Functions¶

\(\mu\)-算子看起来是一个非常无理由的构造：Kleene 似乎无缘无故就弄出了这样一个奇怪的东西，而且它有很好地刻画了递归函数的性质。从数理逻辑角度这事实上有一个好的动机，与前述 Markov 原理的关系也是明显的，但是本文不会从这个角度引申，故而我们采用一种直觉性的讲法：因为递归函数本身是一组递归方程系统的解，所以最小化是必须的。当然，这样看起来肯定是非常生硬的，也不知道后面是否有机会另开专栏讨论构造数学和逆数学、元数学相关的内容，有兴趣的读者不妨自寻 Kleene(1952) 一读。

定义

如果 \(\exists m \in \mathbb{N}, \forall n_1, n_2, \cdots, n_k, g(n_1, \cdots, n_k, m) = 1\)，则称可计算函数 \(g: \mathbb N^{k+1} \to \mathbb N\) 是可最小化的（minimizable）且 \(m\) 最小化了 \(g\)。定义：

\[ \mu m [g(n_1, \cdots, n_k, m) = 1] = \begin{cases} m, \text{where\;} g \text{\;is\;minimizable\;and \;} m \text{\;minimizes\;} g\\ 0, \text{otherwise} \end{cases} \]

命题

如果 \(g\) 可最小化，那么 \(\mu m [g(n_1, \cdots, n_k, m) = 1]\) 可计算。

命题

给定可计算函数 \(g\)，它是否可最小化是不可判定的。

定义

称一个函数是 \(\mu\)-递归函数（\(\mu\)-recursive function），如果它满足以下条件之一：

它是基本函数（basic functions）之一；
它是 \(\mu\)-递归函数的复合；
它是由 \(\mu\)-递归函数递归定义的；
它是可极小化的 \(\mu\)-递归函数的极小化。

定理

一个数值函数可计算当且仅当它是 \(\mu\)-递归的。

TODO: 补全证明，思考更合理的 intuition

程序代数 Program Algebra¶

TODO: 介绍 1901.08840 的结果

推广图灵机：Blum-Shub-Smale 模型 Extending Turing Machines: Blum-Shub-Smale Model¶

TODO: 在更大数域上的图灵机、Mandelbrot 集不可判定