AIT on Infinity and Quantum

作者: LostAbaddon | 来源:发表于2020-03-03 22:04 被阅读0次

因为疫情而在家的这段时间，又看了点关于 AIT 的书，然后想了一些东西，记录下来。

我们可以使用《AIT 中的信息与熵》（或其豆瓣版）中介绍的工具来分析量子图灵机及其关联的信息论。

抽象后的图灵机（以下简称为 CTM）可以表达为这么一种函数：

$T(a) = \{s, b\}$

其中 s 表示运行结果状态，有三种：

2：不停机
1：停机且拒绝
0：停机且接受

而 b 是 s = 0 或 1 时的输出结果，当 s = 2 时 b 为空。

考虑到输出结果总是字符串，所以都可以映射到非负整数（字符集如果有 n 个字符，那任何字符串都可以自然映射到一个长为 l 的 n 进制数，l 就是字符串的长度，所以很显然 0 对应的当然就是空字符串了），我们可以将上述描述图灵机的映射视为从自然数到整数的映射——只需要将代表字符串的自然数加一，而后拒绝态为负，接受态为正，0 表示不停机，这样就可以了。

这样给出的“图灵机”，其实是从功能角度（即从映射关系的角度）而言的图灵机等价类，其实现可以有大量不同的写法。

当然，由停机问题我们可以知道，我们不可能通过图灵机的手段来知道上述映射的全貌，我们只能知道有限个图灵机的完整的映射关系，以及有限个图灵机的部分映射关系，但永远不可能知道所有图灵机的完整映射关系。

现在，很自然地产生了一个问题：既然图灵机可以视为从自然数到整数的映射，那是否所有从自然数到整数的映射都对应一台图灵机呢？

答案显然是不能。

我们将标准意义上的图灵机称为“经典图灵机”，记为 CTM（CTM 为全体 ctm 的集合）。而将这类映射函数称为“经典映射机”，记为 CMM（同上，CMM 为全体 cmm 的集合）。

CTM 的数量，很显然，是可数无穷个，即 $\aleph_0$ 。而 CMM 的数量则是 $\aleph_1$ 个。所以显然并非所有 cmm 都是 ctm，而是存在不可数无穷个 cmm 不是 ctm。

这里可以看出，之前的文章所讨论的其实是 CMM 构成的有向图上的跳跃问题，而不只是由 CTM 构成的有向图上的跳跃问题。

我们下面开始考虑神谕机 Oracle。

我们用 $\mathrm{CTM}_{\alpha, \beta}$ 表示加装神谕机 $\alpha$ 与 $\beta$ 的（即图灵跳跃后的）图灵机构成的集合。由于神谕机一样可以表达为将自然数映射到整数的函数，所以虽然存在无穷台神谕机都无法用图灵机来表示，但任何一台神谕机都可以表达为一台 cmm，而加装了任意有限台神谕机的图灵跳跃后的 $\mathrm{CTM}_{\lambda...}$ 的数量都是可数无穷的。

也就是说，CMM 比加装了任意有限台任意功能神谕机的图灵机都要大：

$\mathfrak{CTM} = \bigcup_{\{ \lambda \}} \mathrm{CTM}_{\{ \lambda \}} \subset \mathrm{CMM}$

由于任意 ctm 总可以编码为一个自然数，所以任意 ctm 都可以作为任意 cmm 的输入。而神谕机本身可以作为新的符号添加到字母表中，所以加上任意有限数量任意功能神谕机的图灵机原则上也都可以表达为自然数，因此也都可以作为 cmm 的输入。而与此同时，并非所有的 cmm 都能编码为自然数，所以并非所有 cmm 都能作为 cmm 的输入。

这也就是说，在 $CMM \cap \overline{\mathfrak{CTM}}$ 中可以存在特定的映射机，它能判定任意输入的 ctm 或 $\mathrm{ctm}_{\{ \lambda \}}$ 是否会停机；同时由于它位于 $\mathfrak{CTM}$ 之外，所以它本身及所有包含它的 cmm 都无法作为任何一台 cmm 的输入。

这就是说，CMM 的算术阶层至少是 $\Sigma_2^0$ 的，而且很可能就是 $\Sigma_2^0$ 的，虽然我还没证明这点。

$\Sigma_2^0$ 大致可以理解为所有如下形式的关于自然数的原始递归函数有解的自然数集所处的算术阶层：
$\exists m_1 \exists m_2 ... \exists m_a \forall l_1 \forall l_2 ... \forall l_b \exists n_1 \exists n_2 ... \exists n_c P(x, m_1...m_a, l_1...l_b, n_1...n_c)$
而 $\Sigma_1^0$ 只有一层存在谓词而不需要两层，且对应的是所有图灵机构成的集合（由MRDP定理可知）。在 $\Sigma_1^0$ 与 $\Sigma_2^0$ 之间存在不可数无穷个图灵度。

因此，我们现在得到的成果是：

图灵机及加装任意有限数量台任意功能的神谕机的图灵跳跃后的图灵机都是 CMM 的自己
CMM 中存在不能作为任何一台 cmm 输入的 cmm，且它可以判断任意图灵机及加装任意有限数量台任意功能的神谕机的图灵跳跃后的图灵机是否停机
CMM 的算术阶层至少是 $\Sigma_2^0$

下面一个很自然的问题，就是是否能构造出一台机器，它能以所有 CMM 为输入，并得到有意义的结果？

且，更重要的是，就像 CMM 可以划分为 CTM 及各种加装神谕机的 $\mathrm{CTM}_{\{\lambda\}}$ ，那些更高层级的机器是否也存在复杂的结构呢？

我们首先要做的，是对 CMM 进行编码，将 CMM 映射到实数或其某个连续子集上。

对于任意一台 cmm，我们可以建立一个序列 $\{M_i\}$ （i 从 1 开始），其第 i 位的值就是当输入为可以编码为 i - 1 的字符串时的输出所编码成的整数（请记住，正数表示接受，负数表示拒绝，0 表示不停机）。因此，我们需要将这 $\aleph_0$ 位长的 $\aleph_0$ 进制数编码到实数或其连续子集上。

这样的编码并不难找，比如下面这种：

$\begin{cases} e(n) = \mathrm{sign}(n) \left( 1 - 2^{- |n|} \right)\\ N(M) = M_1 + \frac{1}{2} e(M_2) + \frac{1}{3} \sum_{i = 3}^\infty 2^{2 - i - \sum_{j = 2}^{i - 1} |M_j|} e(M_i) \end{cases}$

这样的编码可以在 CMM 与实数之间建立起一一映射关系。尤其，我们可以将固定字符串视为将空字符串映射到自身、而将所有非空字符串映射到不停机的特殊的 CTM，那它在 CMM 中的编码和它在 CTM 中的编码将是一样的，都是 n。

由此，我们就从离散的 CTM 迈入了连续的 CMM 的世界。

这里还可以考虑一个有趣的问题：如果连续统假设不正确，那会发生什么？
如果 CH（即“连续统假设”）不成立，比 $\aleph_0$ 大的最小的基数我们记为 $\aleph'_1$ 。而上面我们得到的 CMM 数量为 $\aleph_1 \neq \aleph'_1$ ，因此理论上或许存在某一类机器，其数量为 $\aleph'_1$ ，且它可以以 CTM 为输入和输出，但 CTM 和 CMM 都无法以它为输入或输出。它包含在 CMM 中，但我们无法通过加装神谕机的方式来构造出来，而同时它又可以编码为实数，但我们却不知道它到底是什么——想想就觉得很神秘。
尤其，我们知道算术阶层 $\Sigma_2^0$ 中包含了停机问题，而 $\Sigma_2^0$ 与 $\Sigma_1^0$ 之间包含了不可数无穷多个图零度，所以如果连续统假设不成立，那 $\Sigma_2^0$ 可能在位于这 $\aleph'_1$ 个位于中间层的映射机中。

既然我们已经将 CMM 映射到了实数，那下面自然就可以问：将 CMM 映射到 CMM 的函数是什么样的？很显然，就是能将实数映射到实数的函数，其这样的函数有 $\aleph_2$ 个，所以并非所有这样的函数都是 CMM。

这样我们就自然建立了一种将映射机不断提升到更高层级的方式： $\mathrm{CMM}_{n+1}$ 是能将 $\mathrm{CMM}_n$ 映射到 $\mathrm{CMM}_n$ 的所有函数的集合， $\mathrm{CMM}_1 = \mathrm{CMM}$ ，且 $\mathrm{CMM}_n$ 的数量为 $\aleph_n$ 。

但这样的结论其实作用不大，因为更有意义的问题是：对于给定的 n， $\mathrm{CMM}_n$ 拥有什么样的结构？

我们已经看到，CMM 可以被 CTM 和神谕机分解出不可数无穷个图灵度，且彼此之间构成了不可数无穷条彼此独立的图灵跳跃链条。因此，在从 CMM 到 CMM 的映射构成的集合 $\mathrm{CMM}_2$ 中，很有可能也存在这样的结构，而且可能更加丰富。

在讨论 $\mathrm{CMM}_2$ 的结构之前，我们先来回头看一下最经典的图灵机：CTM。

CTM 是 CMM 的一个真子集，是将自然数映射到整数的一类特殊的函数。其传统定义是一个七元组，我们可以将它略加调整，写成这么一种形式：

一台图灵机，由一组数量有限的状态，与一组操作构成；
每一种操作，都可以将图灵机的状态映射到新的状态；
状态中的一部分，被视为输入，而另一部分则被视为输出。

很显然，我们可以将原始定义中的纸带、读写头位置、内部状态都视为上述“状态”的一部分，只要图灵机运行次数是有限的，这样的状态空间大小也一样是有限的。

因此，我们可以将任意一台图灵机拆解为若干台“基图灵机（B-ctm）”有序叠加在一起的序列，每一台 B-ctm 只完成一件最基础的事，实现一次最基础的状态转移，而它们通过可数次叠加，就能构成一台真正的图灵机——如果要叠加可数无穷次，那就表示这台图灵机不停机。

因此，借用《AIT 中的信息与熵》一文中的方法，我们可以这么说：

在由字符串构成的底空间 $\Sigma$ 上，选择一组数量有限的 b-ctm 作为图灵结构， $\Sigma$ 的一个子集 $\Lambda$ 对应了输入与输出区域， $\Lambda$ 之外的部分都是图灵机正常运行时的中间态——但显然一样可以通过字符串来表达。因此，这样构成的图灵空间 $\left< \Sigma, B-\mathrm{CTM}\right>$ 中的任意（可重复）序列 $\{B_1,B_2...\}$ 若能将一个 $\Lambda$ 中点映射到 $\Lambda$ 中另一个点，则称该序列为一台 CTM。而上述序列称为这台 CTM 的基表达。

关于目标区域 $\Lambda$ ，很显然它包含了所有小于等于 0 的部分，而在正数部分中则只包含一小部分，因为存在大量计算机内部状态需要被编码进的区域。

因此，加装神谕机可以视为给图灵结构添加新的 ctm——有些 ctm 无法通过原有图灵结构的有限次跳跃获得，从而就得到了图灵跳跃后的图灵机。

有了这样的新的视角后，事情就变得有趣了起来。

我们先来看跳跃次数。

传统上，一台 CTM 如果能停机，当然是指它能在有限次运算后停机，对应的就是其基表达长度有限。那，一个很自然的问题就是：如果基表达长度无限，会怎么样？

注意，基表达长度无限，不表示该图灵机的代码长度无限，所以它还是 CTM 而非 CMM。

无限长基表达当然对应了该 CTM 不会停机了，但这并不表示这个序列不能给出有意义的结果，比如在不考虑计算精度问题的情况下，下面这段伪代码就可以给出可数无限次运算后输出有意义结果的情况：

fun = () => {
    var i = 0, j = 1;
    while (i < 2) {
        i += j;
        j /= 2;
    }
    if (i > 2) return false;
    return true;
}

显然，这段代码在有限次执行的情况下不可能停机，但如果我们允许基表达长度取到可数无穷，那它就能“停机”并返回结果：true。而有些程序，即便允许执行可数无穷次，也依然不会停机，比如下面这个：

fun = () => {
    var i = 0, j = 0;
    while (i < 2) {
        i += j;
        j /= 2;
    }
    return true;
}

这段代码和上面的唯一区别，就是这次 j 的初始值为 0，从而无论执行多少次，i 的值都不会变，因此即便这段代码执行了可数无穷此，它依然不会停机并返回结果。

这也就是说，并不是所有 CTM 在允许可数无穷次运算后都不停机，也不是所有 CTM 在允许可数无穷（ $\omega$ ）次运算后都会停机。

甚至于，我们还可以构造出需要执行更多次数才能停机的 CTM：

fun = () => {
    var i = 0, j = 1;
    while (i < 2) {
        let m = 0, n = 1;
        while (m < 2) {
            m += n;
            n /= 2;
        }
        i += j;
        j /= 2;
    }
    return true;
}

它要停机的次数为： $\omega^2$ 。

还能不能更大？当然可以：

fun = () => {
    var i = 0, j = 1;
    while (i < 2) {
        i += j;
        j /= 2;
        fun();
    }
    return true;
}

由于迭代次数是可数的，所以这个函数需要执行 $\omega^\omega$ 次后才会停机并返回 true，也就是说，它停机所需的执行次数，即它的基表达长度，为不可数无穷大，或更准确地说就是 $\aleph_1$ 。

但，它还是会停机的，如果我们将 while 条件 i < 2 修改为 i < 3，那就是不会停机——执行不可数无穷大阶无穷大次也不会停机。

因此，如果我们将“停机”的概念，从执行有限次，替换为允许执行无穷大次，而且是不可数无穷大次，那情况会变得很特别。

我们现在可以将 CTM 是否会停机的状态修改为三种：

停机：基表达长度有限；
本质停机：基表达长度为无穷大时可完成执行并停机；
不停机：即便基表达长度为无穷大也不会停机。

用物理上的例子来说，可以这么类比：

停机：平坦时空中朝坐标原点匀速直线飞去的质点可以在有限坐标时间内抵达原点；
本质停机：施瓦西时空中朝着黑洞中央匀速直线飞去的质点在有限坐标时间内无法抵达黑洞中央奇点，但可在有限长本征时内抵达；
不停机：施瓦西时空中大量绕着黑洞做椭圆或双曲线运动的质点，它们永远不可能抵达黑洞中央奇点。

而且，从上面的例子可以看出，本质停机的 CTM 在停机时长上也分三六九等。我们可以为本质停机的难易程度指定一个量，称为 CTM 的“停机难度（HD）”。显然可停机的 CTM 的停机难度为 0，本质停机的 CTM 的停机难度大于 0，而不停机的 CTM 的停机难度为无穷大——这个无穷大有多大？不知道，反正是不可计算的。

而，前面第一个给出的需要执行 $\omega$ 步才停机的 CTM 的停机难度为 1，最后给出的需要 $\omega^\omega$ 步才停机的 CTM 的停机难度为 2。显然中间那个需要 $\omega^2$ 步才能停机的 CTM 的停机难度依然还是 1。是否存在停机难度超过 2 的 CTM 呢？反正目前还没想到，但应该是存在的。

我们可以模仿 Chaitin 常数来构造一个基于停机难度的新的停机常数：
$\Omega_{HD} = \sum_{i = 1}^\infty 2^{-i} 3^{- \mathrm{HD}(i)}$
和 Chaitin 常数一样，这个停机常数显然也是不可计算的。停机常数的第 i 位上的值，是 i 对应的图灵机的停机难度的函数，当它停机时为 1，不停机时为 0，而对于本质停机的情况，则可能为 1/3、1/9 等值。由于 3 和 2 互质，所以这样给出的编码对于停机情况的描述是唯一的，而且如果将本质停机归为不停机的话，给出的就是 Chaitin 常数。

显然，但一台图灵机的停机难度大于 0 时，它是可能出现一些超越 CTM 的行为的——因为无限次操作的极限，可能超出原来的集合范围。

比如说，如果我们将 CTM 限制在四则混合运算的范畴中，那原本无理数是 CTM 无法精确计算的存在，但当允许停机难度为 1 的 CTM 存在时，无理数便可能存在——它们是有理数序列的极限。

因此，通过允许停机难度大于 0 的 CTM 的存在，我们发现原本是从自然数到整数的映射，现在变成了从自然数到实数的映射。我们用 $\mathrm{CTM}^{(n)}$ 代表停机难度不大于 n 的图灵机构成的集合，因此 $\mathrm{CTM}^{(1)} \subseteq \mathrm{CMM}_1$ 。

而另一方面，我们除了可以将图灵机的基表达的长度拓展为无穷，还可以选择拓展一个图灵空间的图灵结构。

在《AIT 中的信息与熵》中我们提到过，可以将 CTM 进行分解。因此，如果图灵结构中不可分解的 B-ctm 的数量达到可数无穷个（对应我们允许字母表无限长，操作符无限多，或者加装无限多台神谕机），那此时有限长的图灵机的数量也依然是 $\aleph_0$ ——除非我们允许图灵机编码的长度为无限长，才有可能真正在数量上从 CTM 提升到 CMM。

当然，数量不足并不能说计算能力不行，万一里面就有一台图灵机能做到有限长字母表做不到的事呢？

对于有限范围的输入，CMM 和 CTM 并没有什么区别，因为只要将一台 CMM 对所有可能的有限范围输入都跑一遍，得到的结果自然可以用一台 CTM 来实现——因为此时输入到输出的映射总是可以表示为有限长映射表的，所以可以用 CTM 来实现。

因此，要超越 CTM 的计算力只可能对于可数无穷长的输入具有足够的处理能力。因此，如果我们允许一台神谕机，能对不可压缩长度为可数无穷长的输入做出分类与相应的处理，那原则上加装了这台神谕机的图灵机就拥有了超越 CTM 而进入 CMM 领域的能力，因为对无穷长输入的处理能力是 CTM 不可能具备的。

让我们重温一下，图灵机可以看作是在图灵空间中的一组基图灵机构成的可重复有限长序列，能将空间中一个点映射到指定区域内的某个点。这个图灵空间的图灵结构给出了一台图灵机可以进行的基础操作都有哪些，加装神谕机便是拓展图灵结构。

我们下面用基表达 $\{T_1,T_2...\}$ 来表示一个从指定起点（ $T_1$ ）开始的图灵机，实际上它给出了图灵机的运行状态，而不是图灵机的“代码”。

由于 CTM 也可以用自然数表达，输入数据也可以用自然数表达，因此我们可以定义图灵空间中两个自然数的“乘法”为（ $N$ 代表从图灵机到自然数的编码映射）：

$n_1 \times n_2 = N(n_2(n_1()))$

显然，这样定义的“乘法”显然是非阿贝尔的。

我们虽然称其为“乘法”，但图灵空间目前并没证明可以在该乘法作用下构成群。

这样，我们就可以说停机图灵机就是有限个自然数的有序乘积，而停机难度等于乘数序列的基数的阶加 1。

这样的序列可以是图灵机，自然，也可以是“证明”过程。

至此，我们终于可以讨论 $\mathrm{CMM}_n$ 这种超大范畴中的分层问题了。

从上面的讨论我们知道，一个由映射机（包含图灵机）构成的集合 $CT$ 中，我们可以选其子集 $BT$ ，并通过 $BT$ 中元素的可重复有限序列来将 $BT$ 拓展为 $BTX$ ，通过这个方法可以将 $CT$ 分解。

比如，我们取 $BT$ 为所有将图灵机的编码加自然数后映射回图灵机的图灵机， $CT$ 是所有整数，则 $CT$ 显然只有一类；而如果将 $BT$ 取所有将图灵机的编码乘自然数后映射回图灵机的图灵机，那 $CT$ 就不一样了，每个素数都可以由此张出一类子集。

当然，这两个例子只是示例。实际情况中， $BT$ 可以是一大类映射机，比如 CTM 集，而将 $CT$ 选为 CMM，那由 CTM 的特性可知，它将 CMM 根据图零度分解成了不可数无穷类。

同理，在 $\mathrm{CMM}_2$ 中肯定也存在这样的结构，存在一类映射机 X，其数量可能是 $\aleph_0$ 或 $\aleph_1$ 个，计算层级与 CMM 相同，且能将 $\mathrm{CMM}_2$ 分解为不可数无穷多类，对应不可数无穷多个图灵度。

下面的问题就是， $\mathrm{CMM}_2$ 中这种能与 CMM 中的 CTM 位置对应的映射机集应该如何构造。

我们下面将图灵机的样子再改变一下。

在上面我们尝试将图灵机是状态改变机，将纸带与内禀状态统一在一起。我们下面则反过来，继续认为纸带与内禀状态是分开的。

我们可以将纸带视为“外部时空”，而内禀状态则是“粒子状态”，读写头位置就是“粒子在时空中的位置”。

这样，图灵机，或者更准确的是说图灵机的基表达，对应的就是在粒子在时空中的运动轨迹。

图灵机的每次运动，都会改变读写头所在位置纸带上的信息，这对应了粒子对时空（及时空上规范场）的影响；图灵机每次计算对内禀状态的影响，对应了粒子本身状态的改变；而图灵机每次计算最后对读写头位置的改变，则表现为粒子在时空中被时空与规范场相互作用后发生的位置改变。

因此，连续化之后的 CMM 如果视为包含粒子的连续时空的话，那 $\mathrm{CMM}_2$
对应的就是从一种这样的时空到另一个这样的时空的所有可能映射的集合。

于是，上面的问题就变得明晰了：选定一套时空与粒子的动力学规则，以及一组初始状态，这样能生成的所有状态是否能覆盖所有可能出现的时空与粒子状态？

需要注意的是，这里虽然用了“时空”、“粒子”等物理词汇，但实际上这个问题和物理并没有太大关系。

我们如果将最“基础”的运动视为只有引力相互作用中的粒子与时空的运动，那么各种规范场可以视为在这个系统中加入的“神谕机”，它能将一些本不可能出现的时空与粒子状态构造出来。

这个思路看起来挺有趣的，但目前没法证明它到底靠不靠谱，因为这种对应纯粹是文字性的。

但，我们可以合理地推测，只要对 $\mathrm{CMM}_2$ 中的映射机加上恰当的约束，那这样得到的映射机集合在有限长的联合作用后，也无法将整个 $\mathrm{CMM}_2$ 覆盖。我们现在只不过对于这样的约束到底是什么还不清楚。

更进一步，从 $\mathrm{CMM}_2$ 到 $\mathrm{CMM}_2$ 的映射，即 $\mathrm{CMM}_3$ 的情况就更丰富了。而且，如果我们将每一个 $\mathrm{CMM}_1$ 都编码到实数的话，那 $\mathrm{CMM}_3$ 中的元素就是函数到函数的映射，即泛函，这不由得让我们想到了一个自然界中最常见的泛函——量子路径积分。

一台量子图灵机（QTM）的结构，可以是在 CTM 上添加一些具有量子计算能力的神谕机，且允许将处于量子叠加态的字符串作为输入和输出使用。但从另一个角度来看，量子映射机的定义就显得简单了很多：

$\mathrm{QMM} = \{ Q : F \times R \rightarrow F \times R \}$

其中 F 是一个代表量子几率幅的域。

那么，一个很显然的问题，就是 QMM 的计算力是否超越了 CTM？

由于 QMM 是在 CMM 的基础上增加了量子态，所以其输入可以视为自然数的量子叠加。

我们用 $\left| n \right>$ 表示自然数 n 对应的字符串，那么输入与输出量子态就可以写为 $\left| \psi \right> = \psi_n \left| n \right>$ ，这里采用爱因斯坦约定，对 n 自动求和。

这样，我们就可以先将 QMM 分为两类？线性 QMM （LQMM）与非线性 QMM（NQMM）。LQMM 要求：

$\hat Q \left( \psi_n \left| n \right> \right) = \lambda \psi_n \hat Q \left( \left| n \right> \right)$

这里 $\lambda$ 是量子几率幅的归一化系数。不难证明，每一台 LQMM 都可以表达为一组 CMM 的量子叠加：

$\forall \psi_i : \exists \rho_r : \forall \hat Q : \hat Q \left( \sum_n \psi_n \left| n \right> \right) = \int \sum_i \rho_r \psi_j \left| C_r(j) \right> dr$

其中 $C_r$ 是编码为实数 r 的 CMM。由此，我们可以定义线性的 QTM（LQTM）为：

$\hat Q = \sum_i \psi_i C_i$

这里的 $C_i$ 是编码为自然数 i 的 CTM。LQTM 满足：

$\forall \psi_i : \exists \rho_i : \forall \hat Q : \hat Q \left( \sum_n \psi_n \left| n \right> \right) = \sum_i \sum_j \rho_i \psi_j \left| C_i(j) \right>$

由此可知，LQTM 的算术阶层为 $\Sigma_2^0$ ，因为 CTM 的算术阶层为 $\Sigma_1^0$ 。

事实上，在 LQTM 中“解决”停机问题的方式是显而易见的。

假定算符 $\hat H$ 能判断编码为 n 的 CTM 是否能停机，在 LQTM 体系中其结果为量子叠加态 $\alpha \left| Yes \right> + \beta \left| No \right>$ 。因此，任何一个试图构造悖论的 LQTM $\hat P$ ，由于是 CTM 的线性叠加，所以可以作为量子叠加态输入到 QMM中，因此 $\hat P$ 可以作为 $\hat H$ 的输入。另一方面，由于 $\hat P$ 是线性的，所以我们将得到如下结果：

$\left| \Psi \right> = \hat H (\hat P)\phantom{wa}\\ \hat P ( \left| \Psi \right>) = \lambda \left| \Psi \right>$

也就是说，停机判定的结果，是一台 LQTM 约化在停机与不停机这两个特征态上时的本征态。（当然，这里略去了一些不重要的细节。）

LQMM 中还可能存在一部分不在 LQTM 中，它们是由不是 CTM 的 CMM 通过量子叠加构成的。因此现在 QMM 总共可以分为三类：

LQTM
不是 LQTM 的 LQMM
NQMM

虽然 LQTM 的算术阶层比 CTM 要高，但我们依然可以说任意一台 LQTM 的结果不过是一组 CTM 的量子线性叠加，如果一个问题无法在 CTM 内被解决，那通过 CTM 的量子线性叠加而来的 LQTM 自然依然无法解决该问题。

所以，从能解决问题的角度来说，LQTM 并不比 CTM 强多少——虽然可以在一定程度上解决停机问题，但对于 CTM 无法判定的很多问题，LQTM 也一样无法判定。

更准确地说，如果存在一个态 $\left| n \right>$ ，它作为 CTM 的输入时输出都是相同的，或者它根本不会出现在 CTM 的输出中，那么即便在 LQTM 中这个态也不会有与 CTM 的情况中不同的表现。

对于 CTM 中的不一致性，LQTM 可以通过量子叠加来缓解甚至解决相关问题，但对于 CTM 根本无法解决的问题，LQTM 也是无法解决的。所以 LQTM 只能缓解不一致，但无法缓解不完备。

但 LQMM 则不同，它包含大量不是 LQTM 的 LQMM，它们本身就是不是 CTM 的 CMM 的量子叠加，后者的计算能力本就比 CTM 要强很多。

与 LQMM相比，NQMM 的计算力可以更强。

非线性的 QMM 可以认为除了将输入的字符串作为计算条件之外，连输入字符串上的量子几率幅都可以作为输入进行计算，比如下面这段伪代码：

fun = (state) => {
    var p = state.map(s => Abs(Phase(s)));
    var n = max(p);
    for (s in state) {
        if (Abs(Phase(s)) === n) return s;
    }
}

它能将输入量子态中几率幅最大的本征态提取出来。它甚至可以变得非常复杂，比如下面这样：

fun = (state) => {
    var p = state.map(s => Abs(Phase(s)));
    var A = max(p), B = min(p);
    var CTM, Param;
    for (s in state) {
        if (Abs(Phase(s)) === A) {
            CTM = DecodeToTuringMachine(Num(s));
        }
        else if (Abs(Phase(s)) === B) {
            Param = Decode(Num(s));
        }
        if (!!CTM && !!Param) return CTM(Param);
    }
}

将输入量子态中量子振幅最大的本征态对应的编码所对应的 CTM 作为真正操作的 CTM，而将量子振幅最小的本征态对应的编码所对应的字符串作为该 CTM 的输入，并将输出结果作为最终输出结果（一个本征态）。

这样的算法显然不是 CTM 可以实现的。

事实上，如果我们取本征态的数量为 A，那我们可以认为 NQMM 的输入态空间的大小为 $\aleph_1^A$ ，所以基本就是比 A 更高阶的无穷大。

对于任意 $\mathrm{CMM}_n$ 我们都可以构造其量子版 $\mathrm{QMM}_n$ ，其中最简单的部分就是线性叠加构成的 $\mathrm{LQMM}_n$ ，它如上所述，只能缓解 $\mathrm{CMM}_n$ 所有的不一致的问题，但无法缓解 $\mathrm{CMM}_n$ 所有的不完备的问题。而其非线性的部分 $\mathrm{NQMM}_n$ 则拥有更复杂的结构，我们可以猜测 $\mathrm{NQMM}_n \subseteq \mathrm{CMM}_{n + 1}$ 。

最后，总结一下。

我们从功能的视角出发，发现图灵机可以推广为映射机，而映射机整体其实就是从自然数到整数的函数全体。

接着，映射机可以被编码为实数而非整数，所以如果要求映射机本身也能被映射的话，那更高阶的映射机就必须拥有将实数映射到实数的能力，是事实上就是从实数到实数的函数的全体。

反复将上一层的映射机作为操作对象，我们可以不断得到更高阶的映射机 $\mathrm{CMM}_n$ ，它可以将越来越多的东西作为自己的输入和输出，功能也越来越强大。

而从执行次数的角度做推广，我们能得到“停机难度”，它反应了在“有限次操作无法停机”之外更加广阔的关于停机的结构。

而这样推广后的图灵机，自然也会进入到映射机的领域。

接着，我们将图灵机的操作过程做连续化处理，发现由此可以得到高阶映射机很可能有异常丰富的分层与分类结构。

最后，我们考虑量子图灵机与量子映射机，发现每一阶的量子映射机很可能都是更高阶经典映射机的一部分，或者说前者可以被后者描述。

因此，总结而言，从计算能力的角度来说，映射机——实际上就是函数，或者更一般化地说就是范畴态射——的能力足够描述所有我们能想到的计算机器了，从可数的到不可数的，从离散的到连续的，从可停机的到不可停机的，从经典的到量子的。

当然，这种泛泛而谈的东西其实意义也不是很大，因为关于怎么分层、每一层有多少图零度等等问题，其实我们都没有什么答案，这里只是很感性地从数量等角度出发做了一些脑洞分析而已。

本文遵守创作共享CC BY-NC-SA 4.0协议

通过本协议，您可以分享并修改本文内容，只要你遵守以下授权条款规定：姓名标示 、非商业性、相同方式分享。
具体内容请查阅上述协议声明。
纸媒与网络平台如需转载必须与本人联系确认。

AIT on Infinity and Quantum

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

理科生的果壳

有意思的文章