本系列参考的内容主要来自教材《An Introduction to Kolmogorov Complexity and Its Applications》, 外加ai的辅助阅读, 旨在介绍柯尔莫哥洛夫复杂度(Kolmogorov Complexity)的含义, 数学细节, 以及相关应用.

感谢Gemini, 以及其它ai还有我某些不愿意透露姓名的朋友帮助.

什么是Kolmogorov Complexity(KC)？

在给出概念的定义, 我们先来看几个例子.

考虑二进制字符串:

$$ 00000000000000000000000000,\\ 01000110110000010100111001,\\ 10010011011000111011010000 $$

从概率上来看, 这三个字符串产生的概率是相同的, 均为 $2^{-26}$ , 但从人类直观出发, 会觉得第一个字符串更规律. 如果你的注意力不那么涣散的话, 还能留意到第二个序列由$0,1,00,01,10,11,000,...$生成, 而第三个序列是真实的抛一枚硬币所产生的. 从传统概率论的角度来看, 这三者生成的概率是一样的, 但从直觉出发, 前两个序列更加的简单.

而实际上这种直觉也并不是错觉, 在python语言中, 对于第一个式子, 我们有:

print("0"*26)

但对于剩下两个式子, 我们大概率很难将其缩减为像上面这个式子这么简短的形式. 因此, 我们可以粗略用生成一个字符串程序长度来衡量这个字符串的随机性.

显然, 一个字符串存在着很多种生成办法, 为便于比较, 我们不严谨地定义:

在给定描述方法U下, 生成一段字符串x的最短描述长度称为这个字符串的柯尔莫哥洛夫复杂度(Kolmogorov Complexity), 记为$K_U(x)$

描述方法严格定义实际上需要是一个通用图灵机, 而且必须是无前缀的(设 $P$ 是图灵机 $M$ 所有能使其停机的输入字符串（程序）的集合。如果对于 $P$ 中的任意两个不同的字符串 $p_1$ 和 $p_2$，$p_1$ 都不是 $p_2$ 的前缀，那么图灵机 $M$ 就被称为无前缀图灵机。).

自然的, 对于上述表述, 我们会产生以下的疑问:

  1. 假设我定义一种描述方法D, 在这种描述方法下, 定义$a$为$\pi$的前一亿位, 于是我们可以说这$\pi$的前一亿位比只有短短两三位的数字更加简单, 但这明显与我们前面的直觉不符合.
  2. 在能运行c语言或者别的语言, 对于同一个字符串的描述长度显然不同了, 这种定义是否会受到与字符串完全无关的性质所影响?

对于第一种问题, 实际上我们得限制描述方法有着通用性, 更准确的说, 是一个通用图灵机, 但随之而来的另一个问题, 不同通用图灵机明显能够产生不同的描述长度, 而这也和第二个问题相联系, 即我们期望这个定义能够衡量字符串的内在的复杂性, 而这不应该和其它无关字符串的条件有关.

(注:通用图灵机和通用前缀图灵机在计算能力上是等价的, KC(Kolmogorov Complexity)采用通用前缀图灵机只是出于某种理论上的方便)

对于第二个问题, 我们有着如下的定理:

对于任意的两个通用前缀图灵机$U_1$和$U_2$, 存在仅依赖于$U_1, U_2$的常数$c$, 使得对于任意字符串$x$有:

$$ |K_{U_1}(x)-K_{U_2}(x)|\leq c $$

即在相差一个加性常数的前提下, 不同通用前缀图灵机下的字符串x的KC是相等的

KC的有趣推论

返回到我们上面的例子, 考虑长度为n的全为0的二进制字符串, 无论是采用python的:

print("0"*n)

或者是其它语言的循环语句, 实际上所需要的描述程序长度的渐进复杂度为$O(\log_2 n)$, 但对于更一般的随机字符串, 除了直接打印以外基本不存在更优的描述方法, 因此, 其描述的渐进复杂度, 或者说KC, 就可以被表示为$\Theta(n)$

下面给出更严格的论述, 需要用到鹊巢原理(或者也叫抽屉原理), 证明略去:

将$n$个元素划分为$k$个组, 其中至少存在一个元素组有大于等于$\lceil \frac{n}{k} \rceil$个

现在, 我们考虑所有长度为$n$的二进制字符串, 并假定通用前缀图灵机$U_1$的程序代码也是二进制字符串, 考虑映射$f$, 如果程序$x$能够停机, 定义$f(x)$为$x$运行在$U_1$上的返回结果

此时注意到所有长度为$n$的二进制字符串一共有$2^n$个, 如果要求每段程序代码$x$在其停机时返回有且仅有一个字符串$f(x)$, 此时由抽屉原理可知也得有$2^n$个程序代码. 从而可以得到至少有一个字符串x, 其满足$K(x)\geq n$

下面给出几个有趣的例子来介绍KC, 需要读者对停机问题, 等主题有所了解

例子1:

如果一个n位二进制字符串$x$的$K(x)$满足$K(x)\geq n$, 那我们称$x$是随机的. 由前面的推论易知, 对于n位字符串, 随机的$x$总是存在的

考虑这样一个形式系统, 这个形式系统足够的强以至于它能够表述"$x$是随机的"这样的命题

假定"$x$是随机的"在这个形式系统里存在着通用的判定方法, 记判定程序的长度为$f$, 如果$x$的二进制表述是n位数字, 此时我们考虑寻找随机的$x$, 易知搜索程序只需要$f+\log_2 n +c$长度即可描述(f个字符编码形式系统, $\lceil \log_2 n \rceil$做输入表示搜索长度为$n$, 而$n$只需要长度为$\log_2 n$二进制字符串来编码, c个字符用来写搜索程序), 其中$c$为转化为搜索程序所需要的额外字符, 即$x$可以用$f+\log_2 x +c$长度的字符串来描述, 从而给定了$K(x)$的上界$f+\log_2 n +c$, 但另一方面, $x$的最短描述长度$K(x)$满足$K(x)\geq n$, 当$n \to \infty$时, 显然有$ n>> f+\log_2 n +c $, 矛盾.

综上, 不存在这样通用的办法能够判定"$x$是随机的"这种命题的.

依据定义, “$x$是随机的"是否为真是可以明确确定的, 但由上述推论, 这个命题却是不可判定的, 这是哥德尔不完备定理在算法信息论领域的一个变体, 一般被叫做柴廷不完备定理(Chaitin’s Incompleteness Theorem)

扩展

下面涉及到的内容不一定与KC相关, 仅作为有趣的扩展进行介绍, 读者需要对语言, 集合论等主题有所了解

引理

引理1: 可数(有限或可数无穷)个可数集合的并集是可数集

参照命题6的证明, 证明来源于(数理逻辑 中国科学技术大学出版社 汪芳庭 P7)

alt text

不可定义数

在数学和逻辑学中，不可计算数（Uncomputable Numbers）和不可定义数（Indefinable Numbers）是两个不同层次的概念。它们都源于一个核心矛盾：有限的描述能力与无限的实数连续统之间的差距。

以下是它们的数学化定义及区别：

1. 不可计算数 (Uncomputable Numbers)

要定义不可计算数，首先必须定义什么是可计算数。

A. 可计算数的定义

一个实数 $x$ 被称为可计算的，如果存在一个图灵机 $M$，对于任意给定的精度 $n \in \mathbb{N}$，该机器能够输出 $x$ 的前 $n$ 位数字（或输出一个有理数 $q$ 使得 $|x - q| < 2^{-n}$）。

  • 形式化描述：存在算法 $f: \mathbb{N} \to \mathbb{Q}$，使得对于所有 $n$，有 $|x - f(n)| < \frac{1}{n}$。
B. 不可计算数的定义

不可计算数是指不满足上述条件的实数。即：不存在任何图灵机（或算法）可以在有限时间内计算出该数的任意精度近似值。

  • 性质：
    1. 数量：因为图灵机的集合是可数的，所以可计算数的集合也是可数的。然而实数集 $\mathbb{R}$ 是不可数的。
    2. 结论：在测度论意义下，几乎所有的实数都是不可计算数。
  • 著名例子：蔡廷常数 $\Omega$（Chaitin’s Omega）, 定义为。它是确定的、有定义的，但它是不可计算的，因为计算它的前n位等价于解决前n位的停机问题。

2. 不可定义数 (Indefinable Numbers)

“定义”是一个比“计算”更宽泛的概念。不可定义数的概念涉及到数理逻辑中的形式语言。

A. 可定义数的定义

给定一个形式语言 $L$（通常是关于集合论的一阶逻辑 $ZFC$），一个实数 $x$ 被称为在 $L$ 中是可定义的，如果存在 $L$ 中的一个公式 $\phi(y)$，使得：

  1. $\phi(x)$ 为真。
  2. 对于任何实数 $z$，如果 $\phi(z)$ 为真，则 $z = x$。
  • 直观理解：你可以用有限长度的话（公式）把这个数唯一地“指出来”。
B. 不可定义数的定义

不可定义数是指在给定的形式系统中，不存在任何有限长度的公式能将其与其他数区分开来的实数。

  • 性质：
    1. 数量：由于任何语言的字母表是有限的，所有有限长度公式的集合是可数的。因此，可定义数的集合也是可数的。(引理1)
    2. 结论：绝大多数实数（不可数个）都是不可定义数。
  • 悖论性：你无法举出一个具体的不可定义数的例子。因为一旦你举出了例子（比如通过某种描述），它在定义上就变成了“可定义的”。这与“理发师悖论”或“培里悖论”（Berry Paradox）有异曲同工之妙。

3. 两者的关系与层级

我们可以将实数集划分为以下嵌套层级：

$$ \text{可计算数} \subset \text{可定义数} \subset \text{实数} $$
  1. 可计算 $\implies$ 可定义： 如果一个数是可计算的，我们总可以用“该图灵机 $M$ 计算出的极限值”作为它的定义。因此，所有可计算数（如 $\pi, \sqrt{2}, e$）都是可定义的。
  2. 可定义 $\not\implies$ 可计算： 有些数是可以被唯一定义的，但无法被计算。
    • 例子：蔡廷常数 $\Omega$。我们可以用数学语言清晰地定义它（随机程序停机的概率），但由于停机问题的不可判定性，我们无法计算它的每一位。
  3. 不可定义 $\implies$ 不可计算： 如果你连描述这个数都做不到，自然也就无法编写算法去计算它。

总结对比

特性 不可计算数 (Uncomputable) 不可定义数 (Indefinable)
核心限制 缺乏算法（步骤） 缺乏描述（名字）
判定标准 是否存在图灵机输出其位 是否存在逻辑公式唯一标识它
典型代表 蔡廷常数 $\Omega$ 无法命名（占实数绝大多数）
集合大小 不可数（测度为 1） 不可数（测度为 1）
逻辑地位 算法信息论研究对象 模型论与集合论研究对象

数学上的直观结论：虽然我们在数学课上学习的所有常数（$\pi, e, \ln 2$ 等）既是可定义的也是可计算的，但在实数轴上，这些“有名字”或“能算出来”的数其实只是极其稀疏的孤岛，剩下的绝大多数实数都是既无法计算也无法定义的。

丘奇-图灵论题与超计算模型

预言机(Oracle machine) 与 图灵度(Turing degree)

为了理解超计算模型的威力, 我们将引入几个例子来说明图灵机的计算局限性, 需要读者对停机问题, 数论基础概念等主题有所了解

假如我们现在拥有了预言(Oracle), 它能够解决图灵机的停机问题, 即对于任意给定的输入, 预言能够判断它在图灵机上是否可以停机, 考虑下面的代码

import itertools

def is_prime(n):
    """检查一个数是否为素数"""
    if n < 2: return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

def can_be_split(n):
    """检查偶数 n 是否可以分解为两个素数之和"""
    for p in range(2, n // 2 + 1):
        if is_prime(p) and is_prime(n - p):
            return True
    return False

def find_goldbach_counterexample():
    """
    哥德巴赫猜想反例搜索器：
    从 4 开始检查每一个偶数。
    如果发现一个偶数不能分解为两个素数之和，则返回该数（停机）。
    """
    for n in itertools.count(4, 2):  # 生成 4, 6, 8, 10... 的无限序列
        if not can_be_split(n):
            return n  # 找到反例，程序在此处【停机】

# --- 一阶预言机 (Oracle) 的逻辑模拟 ---

def first_order_oracle(program_code):
    """
    这是一个假设的预言机函数。
    在现实中，它是不可计算的（停机问题）。
    它接收一段程序代码，并直接返回该程序是否会停机。
    """
    # 假设预言机内部有一种超越算法的能力来判定停机性
    # result = magic_halt_checker(program_code)
    pass

# 解决过程：
# 1. 我们将 find_goldbach_counterexample 的逻辑编码。
# 2. 询问预言：“这个函数在运行后会停机吗？”
# 3. 如果预言返回 True -> 哥德巴赫猜想是【假】的（因为找到了反例）。
# 4. 如果预言返回 False -> 哥德巴赫猜想是【真】的（因为程序永远找不完，说明没反例）。

与一般的验证前有限项上猜想成立是否不同, 上述这段代码在预言机存在时是可以严格证明哥德巴赫猜想的.

某种程度上这也可以理解成一个规约过程, 即对于问题$A, B$如果我们能够解决问题$A$, 那么可以通过某种手段将其转换成问题$B$, 在这里, 哥德巴赫猜想的证明被转化为停机问题, 从直观上看, 我们可以说哥德巴赫猜想比停机问题更"简单”.(注:这只能说明哥德巴赫猜想的证明难度 至多是 需要预言(Oracle)的(或者不严谨地说, “难度上界"是一阶预言机可解的), 但实际上, 根据算法的构造与问题的具体细节, 哥德巴赫猜想的正确性也可能是图灵可计算的, 因而不需要预言也能得到证明)

然而, 事情并总不那么简单, 我们考虑下面一段伪代码:

int H(procedure,Input); // 这里的H函数有两种返回值，死循环(1) 或 停机(0)
int U(P)
{
    if (H(P,P) == 1){ // 如果H死循环
        return 0; // 此时会停机
    }
    else{ // 否则
        while(1){} // 此时会死循环
    }
}

看起来, 上述代码说明了预言从逻辑上就不可能存在, 但这里存在着微妙的差异, 预言判定的是 图灵机 上的给定代码是否是可停机的, 而上面的 H(procedure,Input) 是需要在图灵机上进行实现的, 而预言机本来就不是图灵机能够表示出来的函数, 因此不存在矛盾.

这种逻辑上的微妙差异在于：预言判定的是低阶图灵机上的代码是否停机，而判定函数 $H$ 如果要在同一层级的图灵机上实现，就会陷入自指悖论。然而，预言机（Oracle Machine）本质上引入了超越当前逻辑系统的外部信息，因此它能解决低阶系统的停机问题而不产生矛盾。

我们将带有停机预言的图灵机称为一阶预言机。自然地，一阶预言机也无法解决运行在自身系统（即包含预言调用逻辑）上的代码是否停机，论证过程如上述伪代码。由此，能够解决一阶预言机停机问题的更高阶预言被称为二阶预言。这构成了一个永无止境的图灵跳跃序列。

事实上，只要一个计算模型的能力强到足以表示递归函数（即具备构造对角线程序 $U(P)$ 的能力），那么该模型就永远无法解决自身的停机问题。

然而，对于某些计算能力更弱的模型，情况则截然不同。例如有限状态自动机（FSA），由于其总配置空间是有限的，我们可以通过监控状态是否重复来百分之百地判定其是否进入死循环。再如原始递归函数（PRF）模型，它通过限制循环的无界性，确保了所有程序在构造上就是必然停机的。这些模型能够解决自身的停机问题，代价是它们失去了通用计算的能力。这说明了计算的强大程度与自我认知的完备性之间存在着一种根本性的权衡。

不严谨但直观地, 这可以类比到形式系统的有关结论:一阶逻辑系统是完备的(真的命题都可证), 但拥有皮亚诺算术的一阶逻辑系统却是不完备的(哥德尔不完备性原理).

因此, 由上述论证, 我们可以定义 图灵度(Turing degree) 和图灵跳跃

据下表, 给出一些常见猜想的图灵度:

在计算理论和数理逻辑中，数学猜想的“难度”通常通过它在算术阶层（Arithmetical Hierarchy）中的位置来衡量。一个命题所在的阶层直接决定了解决它所需的图灵度（Turing Degree）。

以下是常见数学猜想的逻辑分类及其对应的图灵度表：

常见数学猜想的图灵度表

数论形式的命题显然可以转化成某种使用计算机能够遍历的问题, 因而可以较为简单地得出其图灵度, 虽然具体的层级会依赖于数论命题的形式,下述对一些原始表述非数论形式的命题给出参考论文, 即猜想能够转化成某种数论形式.

数学猜想 逻辑形式 所需图灵度 证明来源
哥德巴赫猜想 (Goldbach) $\Pi_1^0$ $\mathbf{0}'$ 前面有相关讨论, 略去
黎曼猜想 (RH) $\Pi_1^0$ $\mathbf{0}'$ 等价于某个整数不等式对所有 $n$ 成立, 证明来源:An Elementary Problem Equivalent to the Riemann Hypothesis
费马大定理 (FLT) $\Pi_1^0$ $\mathbf{0}'$ 略
ZFC 系统一致性 ($Con(ZFC)$) $\Pi_1^0$ $\mathbf{0}'$ 询问是否存在一个推导出 $0=1$ 的有限证明。
孪生素数猜想 $\Pi_2^0$ $\mathbf{0}''$ 涉及“无穷多个”，即 $\forall n, \exists p > n$。
考拉兹猜想 (3n+1) $\Pi_2^0$ $\mathbf{0}''$ 涉及“对所有 $n$，都存在步数 $k$ 使其归一”。
P vs NP 问题 $\Sigma_2^0$ $\mathbf{0}''$ 涉及“是否存在算法，使得对所有输入都满足…”。来源参考:The History and Status of the P versus NP Question
丢番图方程是否有整数解 $\Sigma_1^0$ $\mathbf{0}'$ 希尔伯特第十问题 ，已证明等价于停机问题。

费马大定理实际上已经得到了证明, 因而实际上是属于图灵可判定的, 但这里只考虑简单搜索遍历, 所以将其归类到了$0'$

上述图灵度构成的层级可以被称为 算术阶层, 虽然直观看来, 上述层级看起来只是无意义的理论构造, 毫无现实存在的可能性, 但实际上后面对于丘奇图灵论题的讨论中我们可以看到, 某些基于物理理论所构造计算机甚至无法用 算术阶层 来描述, 而不得不引入 超算术阶层 (Hyperarithmetical Hierarchy) 甚至是 分析阶层 (Analytical Hierarchy)

超计算(hypercomputation)

超计算可以简单理解成超图灵计算的, 即超计算可以解决某些图灵不可计算的问题, 比如上述提到的各种数学证明的搜索都可以通过某种超计算机(比如一阶预言机, 二阶预言机)来解决, 后续谈到丘奇图灵论题时会有进一步讨论

丘奇图灵论题

需要读者对丘奇图灵论题有简单的了解.

这里讨论的是比较广义的丘奇图灵论题, 即 宇宙是否是一台图灵机 ?

如果 宇宙是一台图灵机 的话, 那么结论比较平凡, 意味着随处可见的家用电脑都和宇宙本身在根本上是一致的(即二者都能以多项式的时间相互模拟), 区别仅在于效率上的差异

如果 宇宙不是一台图灵机, 而且我们也能够通过某种方式造出 超计算机(hypercomputer), 那么很多数学猜想都可以借由超计算机解决.

为使上述讨论看起来能更加直观而非仅限于某种纯数学理论构造, 下面给出几种可能的超计算机的构造, 它们都基于某种可能的物理假设, 所以依旧是某种理论上的讨论, 不同的是假设换成物理上的假设. 而且哪怕仅考虑理论, 下面给出的模型也存在着某些理论问题, 所以下面谈到的超计算模型也可以当成某种科幻小故事

下面仅会给出简单解释, 具体的物理构造细节可以参考原论文

封闭类时曲线(Closed Timelike Curves)

参考论文:Quantum mechanics near closed timelike lines

封闭类时曲线不严谨地说可以理解成时间穿越, 计算机能够通过某种方式得到来自过去和未来的比特

这是一个基于上面论文的原理的小故事, 用以进行直观理解

小故事——艾丽丝与“哥德巴赫信箱”

艾丽丝的桌子上有一个特殊的“自洽信箱”。这个信箱被设计成一个 CTC（封闭类时曲线）：任何投入信箱的东西都会在几秒钟前从信箱的底部掉出来。

艾丽丝的目标是验证哥德巴赫猜想（即：每一个大于2的偶数都可以表示为两个质数之和）。她准备了一张纸条，上面包含两个字段：[当前检查的偶数 n] 和 [是否找到反例标记 Flag]。

艾丽丝的算法操作：

  1. 接收： 艾丽丝从信箱底部拿起一张纸条。假设纸条上写着 [n, Flag]。
  2. 判定：
    • 如果 Flag 已经是“已找到”，艾丽丝什么都不做，直接把纸条原样投进信箱。
    • 如果 Flag 是“未找到”，艾丽丝开始检查数字 $n$ 是否能分解为两个质数。
  3. 改写：
    • 如果 $n$ 符合猜想（能分解），艾丽丝将 $n$ 加 2，写下 [n+2, 未找到]，然后投进信箱。
    • 如果 $n$ 不符合猜想（这就是我们要找的反例！），艾丽丝兴奋地将 Flag 改为“已找到”，保持 $n$ 不变，写下 [n, 已找到]，然后投进信箱。

奇迹发生了： 艾丽丝刚刚坐在桌子前，还没开始计算，一张纸条就从信箱底部掉了出来。

  • 如果哥德巴赫猜想是错的，纸条上会赫然写着 [那个最小的反例数字, 已找到]。
  • 如果哥德巴赫猜想是对的，情况会变得诡异：艾丽丝会看到一张处于“模糊状态”的纸条，或者根据某种物理选择，她会收到一张写着无穷大数字或处于某种逻辑平衡态的纸条。

艾丽丝不需要遍历无穷，CTC 的因果闭环替她完成了所有时间线上的搜索。

物理解释

根据 Deutsch 的论文，这个故事并非单纯的科幻，它对应着严格的量子力学描述。

  1. 运动学自洽性条件（Kinematical Consistency Condition） 在论文中，Deutsch 提出假设，CTC 内部的量子态 $\rho$ 必须满足不动点方程：

    $$\rho = \text{Tr}_{ext} [U (\rho_{in} \otimes \rho) U^\dagger]$$

    在艾丽丝的故事中，算法的每一步操作（检查、改写、加2）都被编码在幺正算符 $U$ 中。CTC 的物理本质是：大自然拒绝任何不自洽的状态。 如果哥德巴赫猜想存在反例 $n_{crit}$，那么唯有“纸条写着 $n_{crit}$ 且标记为已找到”这一状态能在经过无数次循环后依然保持逻辑自洽。

  2. 停机问题神谕（Halting Oracle）与算术层级 $\Delta_2^0$ 艾丽丝的操作本质上是在运行一个搜索算法。

  • 物理机制： 论文指出，CTC 可以作为判定停机问题的神谕。如果我们将“找到反例并改写 Flag”定义为“停机”，那么自洽性条件会强制系统状态坍缩到那个“已停机”的解上。
  • 逻辑推论： 既然艾丽丝能瞬间得到哥德巴赫猜想的结果，这意味着她的计算能力已经超越了可判定的 $\Delta_1^0$，达到了可以处理 $\Pi_1^0$（全称命题）的 $\Delta_2^0$ 层级, 对应为图灵度为$0'$的计算机 。
马拉门特-霍加斯时空计算机(Malament-Hogarth Spacetime Computer, MH计算机)

参考论文:Non-Turing computations via Malament–Hogarth space-times

小故事——“跨越永恒的视界”

假设宇航员 艾丽丝（Alice） 和她的超级计算机 博比（Bobby） 来到了一颗巨大的、快速旋转的 旋转黑洞（Kerr Black Hole） 附近。

艾丽丝想要彻底解决哥德巴赫猜想。

任务设置：

  1. 博比的角色（计算者）：博比留在黑洞外围的一个稳定轨道上。它的任务是：从 $n=4$ 开始，逐个检查每一个偶数是否能表示为两个质数之和。博比拥有无限的算力燃料和无限的“字条”供应。
  2. 协议：如果博比一旦发现一个反例（即一个偶数不能被分解），它就立刻向黑洞方向发射一个蓝色闪光。如果猜想是真的，它将永远计算下去，永不发光。
  3. 艾丽丝的角色（观察者）：艾丽丝驾驶飞船，直接向黑洞俯冲。她的目标不是掉进最中心的奇点，而是黑洞内部一个特殊的区域——内视界（Inner Horizon）。

故事的发展：

  • 艾丽丝在飞向黑洞的过程中，她看了一眼手表。按照她的时间，她只需要 1 小时就能到达内视界。
  • 由于黑洞造成的时空扭曲，当艾丽丝接近内视界时，外界宇宙的时间在她眼里开始疯狂加速。她回头看去，她能看到博比在轨道上“快进式”地工作：博比检查了前一亿个数字、前一万亿个数字、甚至检查到了宇宙毁灭的那一刻……博比的“字条”堆满了整个星系。
  • 结局 A：在 1 小时还没结束时，艾丽丝突然看到了一道蓝光。她立刻记录下：“哥德巴赫猜想为假，博比找到了反例。”
  • 结局 B：艾丽丝准时到达了内视界的临界点，却始终没有看到蓝光。由于在这个特殊的时空点上，博比那条“无限长”的生命线已经全部落入了她的视觉范围（因果过去），她可以百分之百确定地宣布：“哥德巴赫猜想是真的，因为我刚刚看完了博比耗费无穷时间进行的全部计算。”

艾丽丝在有限的 1 小时内，完成了一个逻辑上需要无穷步的任务。

物理解释

停机问题的判定（$\Sigma_1$ 层级） 论文指出，这种装置本质上是一台相对论计算机（Relativistic Computer）。

  • 证明细节：设 $R \in \Sigma_1$ 是一个递归可枚举集合。博比执行枚举算法。如果元素存在，博比发送信号。艾丽丝在到达 MH 事件 $p$ 之前的任意一刻收到信号则判定 $x \in R$；若到达 $p$ 时未收到信号，则判定 $x \notin R$。
  • 这直接证伪了“物理可实现计算等价于图灵机”的强邱奇-图灵论题。

攀爬算术层级（$\Sigma_2$ 层级） 论文最深刻的部分在于证明了这种计算可以处理更复杂的问题（如 Proposition 2）：

  • 原理：通过设计博比发送两种不同频率/编码的信号（例如 $S_a$ 表示“找到 A”，$S_b$ 表示“找到 B”），艾丽丝在内视界处可以判定包含 $\exists \forall$ 逻辑结构的命题。
  • 这表明 MH 时空不仅能解决停机问题（$\Delta_2^0$），还可以进一步判定算术层级中更高阶的不可计算函数。