随机停机机器的编码定理失效

认识地位与贡献。本文解释了在米哈伊尔·米罗诺夫2026年夏季研究期间得出的算法信息理论中的技术分离结果PIBBSS奖学金.结果有助于AIXI实验室研究项目探讨在面对新事件时，索罗莫诺夫归纳如何从过去的观测中进行推广。
问题表述：科尔·怀斯。
主定理1的证明：GPT-5.6 Sol.
附录证明：时间半测度与随机停止机等价性的证明草稿由 Cole Wyeth 完成，其余部分由 GPT-6 Astra 完成。
写作：Claude Fable 5 和 GPT-6 Astra 草稿，Mikhail Mironov 编辑和重写。
有用的讨论：Aram Ebtekar，Cole Wyeth。
资金与组织：2026年夏季PIBBSS奖学金。

简介

本文研究一种停止复杂性，类似于经典算法信息理论中的柯尔莫哥洛夫复杂性。其动机源自Aram Ebtekar和Michael K. Cohen提出的“黄金手铐”人工智能安全议程。

GH是一种使通用智能体更安全的方法，通过在下文所述特殊情况下将其控制权委托给导师，防止智能体探索新颖的高回报方案或新危险活动。

GH的安全保证通过智能体历史上的简单停止事件来表述：智能体不会在导师触发之前触发可判定的低复杂度谓词。例如，智能体永远不会触发“把铁砧砸到自己头上”，除非导师先触发。

停止复杂性在早期工作中引入，但其安全性应用是GH的新贡献。

一个卡通例子：一名金手铐特工和一个简单的停止事件

GH代理认为其可能的奖励要么属于或等于灾难性奖励。实际上，代理总是从，因此从其视角来看，奖励接近最大值。当灾难性奖励的估计概率较高（即预计未来价值低于某个阈值）时，代理必须呼叫一位安全导师。

想象一个仓库机器人，其历史至今已重复数千次同一流程：抬起一个箱子，放到传送带上，获得奖励。它的传感器从未报告过传送带停滞。

有一天，机器人的优化部分发现了一个捷径：在传送带下放置一个箱子会暂时停滞，并据其估计可能略微提高奖励。传送带首次停滞的时刻在精确意义上是新的：短可计算规则“观察传感器流，并在第一个停滞处停机”正好停在那里。

在普遍先验下，直到该时刻的历史被以不可忽视的权重解释为“世界在第一次停滞前表现如前，之后表现不同”，其中“不同”包括了GH的灾难性奖励。

机器人一直在收集近乎最大化的奖励（来自），因此捷径几乎没有任何收益，主观上却有很多可失去的。悲观的优化器将计划排在常规之下：它害怕自己的计划，不执行它。

如果皮带在机器人没有选择的情况下卡住，机器人就会遇到一个无法排除的新时刻。其预测的未来值跌破GH阈值，机器人将控制权交给导师，即人类操作员，比如说，他会清除堵塞。

从那时起，停滞不再是前所未有的。“第一次停滞”规则不再决定当前时刻，后续停滞则仅由更长规则（“第次停滞”）所决定。对失速的恐惧减少，优化者被允许重新掌控，可能复制导师的行为，即下一次传送带失速时清理卡壳。

衡量一个时刻新颖程度有两种方法：根据其最短停顿规则，或按所有停顿规则总权重。这两项是本文中比较的两个量。

停止复杂性衡量在简单可计算规则被违反时，这可以被解释为一种普遍的新颖性度量，这也促使即使不考虑GH，也支持停止复杂性。

对于普通无前缀机，柯尔莫哥洛夫复杂度与先验概率是相连的：莱文编码定理指出。即，求和中最大的项已经捕捉到整项，且不超过常数因子。

一个带有完整证明的解释是莱昂·朗的关于编码定理的帖子.

在停止机的设定中也可以提出类似的问题。我们使用随机停止机，也就是说我们的程序可以访问无限随机种子。我们将单调停止复杂度定义为在特定字符串上停止的最短程序加种子长度，先验停止概率为所有程序加种子在某字符串上停止的总权重（符号遵循GH定义4）。

那么编码定理的类比是：是否真的？本文证明答案为否定：该间隙不被常数（）限制。

该间隙以有界，以下不等式成立：，其中是整数的普通前缀复杂度（，在中证明）。

先前的工作。分离本身作为陈述并不新鲜。沃夫克和帕夫洛维奇（在其第8节末尾注明）将这种无界间隙归因于米哈伊尔·安德烈耶夫，引用了安德烈夫和亚历山大·申的一篇未发表手稿。

已发表的安德烈夫–波索宾–申论文处理了明文版本，明确推迟了前缀版本。我们不知道有已发表的证明。该证明表明米哈伊尔·安德烈耶夫宣布的结果蕴含。

下面的证明是独立且自包含的。我们声称分离本身没有新意，本文的贡献是易得的证明以及与GH安全构造的联系。

与GH的联系。我们采用GH符号，。验证下文定义与GH定义4在加法常数和乘法常数上一致。

GH安全触发（他们的定理5）用来表述，而可解释复杂度界限（其方程11–12和推论6）使用。表明和不在加法常数内：短停止描述总是满足触发条件，但当新颖质量分布在多个停止标准上，且这些条件都不单独短时，触发也可能触发。

受众。假设对图灵机有基本的熟悉。熟悉柯尔莫哥洛夫复杂性和先验概率是有用的，但并非必需。否则，论证是自包含的。

符号

.和是有限二元字符串和无限二进制序列，是空字符串，是上的一致测度。如果是的前缀，则记为，且如果进一步。字符串可比较，若其中一个是另一个的前缀，则称不可比较（），这恰恰发生在它们在某处不超过两个长度的位置时。

一组两对可比较字符串是链，一组两两不可比较字符串是反链（= 无前缀集合）。深度为的单元格是一个字符串，视为测度的圆柱，或其二元表示以开始的二进制子区间。

注意，当两个单元格的字符串不可比较时，则它们互不相交。

1. 编码定理表述

随机停止机是一种确定性机器，拥有单向只读输入带和单向只读随机带。在计算过程中，它可能会发出三条特殊指令：请求下一个输入位、请求下一个随机位，或停止。

在两个请求之间，它可以计算任意多步（形式上，它是一台拥有两条只读带和一条双向工作带的图灵机），而一次运行可能永远不会停止，也不会再发出请求。

机器只看到它请求过的比特，因此其行为直到任何时刻仅取决于目前消耗的字符串。如果字符串在任意以开头的输入上运行，任意以开头的随机磁带，在恰好消耗了输入和随机比特后停止，则是的见证者;此时我们写为。

对于固定的，见证者构成反链：运行给出的可比见证会随着消耗而停止，且在消耗时停止，因此。因此，见证圆柱是两两不相交的，以下停止概率和停止复杂度定义良好：

示例1。设一次读取输入比特，当最后两个读到的比特均为时停止。它从不请求随机比特。在字符串中停止，且之前没有出现，因此是该集合的指示器。

示例2。设重复：请求一个随机比特，如果是，则停止，否则请求输入比特。它的唯一见证是，因此对每个。

固定一个所有随机停止机的有效枚举及其索引的可计算无前缀码，然后。通用随机停止机从其随机磁带读取部分（如果磁带不扩展的元素，则永运行），然后在输入磁带和随机磁带的其余部分上模拟，这非正式地被解释为的随机种子。

定义

我们称先验停止概率为，单调停止复杂度。该符号与 GH 一致，其定义在常数下与一致（参见）。因此，停机恰好消耗输入的概率是见证和中最大的单项，且是平凡成立的。

编码定理问题询问是否也成立。答案为否定。

非正式（定理1）

对于的最佳单一描述加种子程序，可以任意长于所有程序总质量的总和。

定理1

对于每个常量，存在。等价地，。

该定理通过约简到一个博弈来证明，该博弈依赖于以下两个引理。

非正式（引理2和3）

引理2表明，沿一条输入路径观察停止点的区间是成对不相交的，即它们都保持在描述加种子地址的单一度量单位内。
引理3说明了为什么在我们用通用随机停止机的构造中，“程序加种子”的解释是有效的。

引理2

设为随机停止机，且。若且，则。

证明

假设是可比较的。取一个以开头的输入和一条以较长开头的随机带。对该数据的单一确定性运行满足两个见证者的定义条件，因此它停止了恰好消耗和，因此，形成矛盾。

∎

引理3

当且仅当且。因此和。

证明

一组连续停机，当当它先消耗恰好一个前缀，然后模拟的停机恰好消耗，且恰好消耗，即。该分裂唯一，因为无前缀。∎

特别地表明，不同的枚举选择最多会改变一个加法，最多一个乘法常数。混合公式映射了经典的先验概率图景：前几个随机位以概率指定机器，剩余的随机带作为其种子。

2. 编程游戏

在本节中，我们构建了爱丽丝和鲍勃之间的组合博弈，并声明爱丽丝有一个必胜策略（我们在第5节中证明了这一点）。在第3节中，我们基于爱丽丝的必胜策略证明。

非正式游戏

假设编码定理对某个常数成立（等价地，对于该常数为假）。爱丽丝试图反驳编码定理，鲍勃试图为其辩护。爱丽丝宣称在处的总质量为，然后鲍勃用权重至少为的短程序加种子回答。

也就是说，鲍勃的折现因子为。

注意，沿每条路径的总质量最多为，因此 Alice 对她的声明有相应的约束。

鲍勃回答的约束是：对于可比字符串，他的答案必须不可比。

博弈（）。爱丽丝的走法是一个权重为的声明，，，。每个字符串最多声明一次。爱丽丝对每条路径上的总权重有以下约束：

鲍勃会立即用字符串、，且在不同可比较字符串上的答案必须是两两前缀不可比较的。如果鲍勃没有合法答案，爱丽丝获胜。

定理4

对于每个，存在使得 Alice 在中拥有一个可计算的获胜策略，且所有路径负载最多为（我们精确定义于）。

定理4在第5节中已证明。现在我们假设为真，并基于此证明。

3. 对角化：定理4⇒定理1

非正式（定理4⇒定理1）

（第5节证明）指出，对于每个，爱丽丝都有必胜策略。对每个，在标签处同时运行爱丽丝策略，在不相交子树中，即在，她的声明汇聚为一个较低半可计算的时间半测度。

根据附录中证明的，一个l.s.c.时间半测度等同于某个机器的停止概率。记为的描述长度。注意包含在中，系数为。爱丽丝在标签上的胜利，参数使得其超过的量超过。

因此，它也超过的。由于爱丽丝对每个都获胜，这证明了。

该算法可无限运行，并从下（初始处处）枚举质量函数。算法与每个，在以标签为根的子树内，采用爱丽丝的 -策略。这些标签形成反链，因此每条无限路径最多进入一个子树。

当 Alice 的参数 -策略宣告时，算法：

赋予其中（因此每个单位最多接收一次质量），
通过燕尾搜索所有字符串，寻找一个作为W.R.T.的见证者，
如果找到了，记为鲍勃的答案，并让策略继续。如果没有这样的证人，搜索将无限期进行，对应于爱丽丝在此标签中的胜利。

假设第二步找到当前，设是在与相当的顶点上的任何早期记录答案。则和是可比较且不同的，应用到得到。对于每个搜索可能找到的，这都成立，因此在每个标签上，记录的转录记录都是某个 Bob 的合法操作。

对于每个爱丽丝的策略，在有限个声明内击败鲍勃。在算法运行过程中，对于每个，定义为鲍勃第一个无答案的声明。即，没有证明满足。

因此：

引理5

对于某个机器。

我们在第四节通过对随机机器停止概率的刻画来证明。

固定，令。注意不依赖于。混合物项（）给出对所有、和，因此

将（2）和（3）组合：。由于这对所有都成立，证明了。

备注6

的间隙以有界，以下不等式成立：，其中表示整数的普通前缀复杂度。证明见于。该上界是否锐利尚悬而未决。

4. 引理5证明：时间半测度

如果对每个，则称时间半测度为。

考虑任意随机停止机。在一个输入流上，事件“停止恰好消耗”是互斥的，因此是时间半测度。也通过枚举见证者，是更低的半可计算的。

反之亦然：

等价定理（已在中证明）。函数是较低的半可计算时间半测度当且仅当对某个随机停止机。此外，可以从的近似指标计算。

的证明。根据等价定理，只需证明是一个 l.s.c. 时间半测度。事实上，在延伸的路径上，质量是对的一种策略的声明，总总数不超过（），且延伸无标签的路径不携带质量。

因此是一个 l.s.c. 时间半测度，因此对于某个机器。∎

5. 定理4证明：爱丽丝获胜

我们引入一个辅助调色板博弈，并构造 Alice 的必胜策略。之后我们将将博弈转换为，从而证明 Alice 获胜。

非正式（调色板游戏）

与的博弈相同，但 Bob 用精确大小的单元格回答，Bob 使用不同的单位区间，其中扮演折扣因子的角色。我们引入是因为对进行归纳攻击更容易。

调色板博弈（）。鲍勃获得了单位区间（调色板）的不相交副本。爱丽丝的声明如中所示，路径预算相同（1）。鲍勃回答格、、，且在不同可比较顶点回答的格子必须不相交。

爱丽丝如前所述获胜。

注意精确权重：由于，鲍勃的答案恰好占用测量，对应于（而非至少）。

非正式（引理7）

爱丽丝在鲍勃拥有的多少色彩上都胜过鲍勃。她在每条路径上都保留了一小部分预算未花，这正是入选者所需要的宽松。

引理7

（调色板消去。）对于每个，存在一个可计算的Alice策略，使得Bob失败，且所有路径载荷最多为，其中。

我们在本节末尾形式上推导。目前我们提供一个简短的非正式证明。之后通过归纳法证明。

非正式（引理7中定理4的证明）

引理7说爱丽丝获胜（我们用），定理4说爱丽丝赢。

我们想将两位玩家从中的所有走法平移到，并使用爱丽丝的获胜策略。爱丽丝的声明在两局游戏中相同，因此无需翻译。鲍勃的法律答案为。

我们用零填充其长度恰好为。几何上，是长度至少为的二进态区间，零填充将其修剪到长度恰好为的左边子区间，这只会让鲍勃更容易满足不相交。

长度为的区间恰好位于其中一个块内。我们将每个块重新缩放到单位区间，以得到的调色板。填充字符串的开头位命名块（调色板索引），其余位是块内的地址。

单位区间被切割成多个部分，鲍勃的回答被精确剪辑，也同样如此。

通过归纳法证明，构建所有声明大小相等的策略（因此所有鲍勃的答案深度最多为，且所有路径载荷最多为。

基底。声明。没有调色板，因此没有答案;且。

步进。设为调色板的策略，指数最多为，负载受限。我们构造Alice的获胜策略。修正

深度单元称为粗细胞，因此每个调色板包含粗细胞，所有调色板中总共有粗细胞。深度单元称为细细胞，因此每个粗细胞包含细细胞。

第一阶段展示了爱丽丝如何制造一种情形：她在某条路径上只使用权重，而鲍勃沿该路径的回答接触到N个总测度为1（相当于一个调色板权重）的不同粗胞，而这些单元格在第二阶段无法使用。

具体来说，第一阶段构造了一个形如的顶点，使得

它由多个方块组成，每个方块由多个“和一个”组成，在方块末端有一个。
爱丽丝在此前缀上的声明仅出现在1之前的最后一个零（加粗），
爱丽丝的每个声明权重为，所有声明的总权重为，
鲍勃对这些宣言的回答属于不同的粗胞，其总测度为。

第二阶段表明，留给Bob的空间同构于完整的调色板，并且运行在第一阶段构造的顶点的后代上。

第一阶段：将标记强行嵌入不同的粗细胞中

非正式（第一阶段）

假设爱丽丝有声明（标记），每个都为权重，鲍勃的答案位于不同的粗格（标记格）。爱丽丝产生了足够多的新声明，每个声明权重，使得鲍勃的答案无法放入标记的粗格子中，因此对于某个声明，鲍勃将答案置于新的粗格子中。

爱丽丝将该声明命名为第个标记。该构造允许去除所有非标记声明，我们用它来填充鲍勃的粗格子。爱丽丝重复此过程直到有标记。

爱丽丝保持一个活跃顶点和权重——在的祖先处声明（标记），在不同的粗胞（标记胞）中回答。爱丽丝从开始，。给定，设，设

以下链列最深。爱丽丝按此顺序声明，止于第一个答案位于与标记格不同的粗胞中。存在此类（否则鲍勃已失败，爱丽丝获胜）：链顶点两两可比且可与所有标记可比，因此如果所有答案都位于标记粗格内，这些格子将包含两两不相交的细格，但粗格只包含细格。

Alice 保留为 -st 标记，并集合。注意，所有为声明的标记都位于的 -子节点或以下，而未来所有的游戏都将发生在 -子节点以下。

因此，所有的都无法与 Alice 以后声明的所有内容比较（这是最深一阶的点），而的标记，是的祖先，则与所有未来声明保持可比，并持续约束 Bob。

对所有。

路径权重。对于每个路径，上述构造最多有权重声明。对于最大，路径上最大权重最多为

因此，爱丽丝的声明是合法的。通过路径仅携带标记，总负载为。

第二阶段：重新填充清洁电池及电感步骤

非正式（第二阶段）

以下 Alice 想玩。Bob 只能用粗或更大的单元格来回答，因为粗度是用指数界限定义的。不能使用标记粗细胞。未标记粗细胞的总度量是，但它们分布在调色板上。

这对 Bob 没有任何优势，即他最多只能用没有标记单元格（平移映射）的调色板来玩。因此 Alice 可以运行归纳策略并获胜。

如果一个深度为的单元格中没有标记粗颗粒，则称其为干净。

引理8

每一份法律答复对后裔声明的深度回答都是干净的。

证明

这样的声明与每个标记顶点都可比较，因此其答案必须与标记的所有细致答案不相交。假设遇到一个标记粗胞。一个深度为的单元仅通过包含深度单元与深度单元相交，因此。

但包含 Bob 的精细答案，因此也包含该答案，与不相交性相矛盾。∎

恰好粗胞是无标记的。设为最大洁净胞的集合（洁净且父阶不洁，调色板根具有深度）。每个调色板内存在反链，下面的深度单元正是无标记粗胞，因此

这与调色板的总测量值相同。干净区域是参差不齐的，而期望调色板保持完整。下一个引理和平移映射修正了这个问题。

非形式（引理9及平译映射）

将最大净细胞从大到小排序，并从左到右排列到新的单位区间。非递增顺序的二元大小保证每个最大净细胞都会映射到这些新鲜单位区间中的一个单元。

引理9

（重新打包。）取新调色板：单位区间的新副本，与 Bob 调色板无关。存在两两不相交的新调色板单元格（），。

证明

将调色板与并以非递减深度处理（平局由调色板索引打破，然后按字典序）处理，从左到右分配连续长度区间。当放置长度-区间时，所有之前的长度都是的倍数，因此其左端点也是 1。

因此区间不能跨越整数，因为整数也是的倍数。通过（5）区间恰好铺砌。∎

设（）为通过证明生成的单元格;我们称的重装副本。现在定义一个从干净单元到新调色板单元的平移映射，在该映射下，剩给Bob的干净区域映射为完整的调色板。

每个干净单元都有唯一的最大净祖先。如果，则。写作，集合

位于重装副本下方的同一相对地址的单元格。这样则保持深度，并在两个方向上保持可比性和不相交性。

归纳步骤。爱丽丝下了翻译为的，将鲍勃的答案（深度干净且指数绑定）输入虚拟调色板博弈。根据的性质，合法的实着子变成了合法的虚拟出牌，因此得出一个没有法律虚拟答案的声明。

一个合法的实答案是干净的，并且会映射到一个合法的虚拟答案，因此不存在，爱丽丝获胜。

载荷。第一阶段中不经过的路径服从（4），因此其负荷最多为

通过的路径携带标记权重加上路径载荷，总共最多为

因此，所有路径载荷最多为。

该策略使用声明，最多为，根据构造是有限的，并且在中可均匀计算。

剩下的推导是：爱丽丝在调色板博弈中的胜利意味着她在博弈中的胜利（该证明的非正式版本见上文，在的陈述之后）。

定理4的证明（引理7）

设。爱丽丝通过将其翻译为获胜：她运行她的 -策略，将她的声明从复制到（两局游戏中的声明格式和预算相同（1），并将鲍勃的回答翻译到它们在中的阴影中，定义如下。给定一个合法的 -答案，将其扩展为长度恰好为（可能，因为），并拆分，，。的阴影是调色板中的单元格，深度恰好符合要求。注意零填充保持不可比较性，因为不可比较字符串在两个长度中的位置不一致，填充在该位置不变。填充字符串是不可比较的，当当（前位内的不一致）或和。

因此，法律鲍勃-答案在不同可比较顶点的阴影在中是合法的：如果在，则填充字符串不可比较，因此阴影位于不同调色板或是同一调色板中的不相交单元。

因此，爱丽丝的-策略适用于阴影平移，最终在中做出没有法律鲍勃答案的声明。鲍勃在两者中都没有法律答案：该答案的阴影在中是不存在的法律答案。

因此爱丽丝获胜。∎

该构造属于由Gács和Day开创的间隙定理家族，采用了Vereshchagin精神的博弈论方法。

附录

时间半测量和随机停止机

回想第4节，时间半测度是一个函数，对每个。如果第二个参数中存在一个可计算的，且对所有，则时间半测度为下半可计算（l.s.c.），且对所有。

我们归一化，并假设每步近似只增加一个字符串，且以二进量增加。这并不损失一般性：用不超过的最大倍数替换，保持可计算且不可递减的，且在相同上确界，且多条字符串递增的步骤可拆分为多个步骤。

等价定理。函数是较低半可计算时间的半测度当且仅当对某个随机停止机。此外，可以从近似的指标计算出。

证明，机器到半测度

固定一台机器。见证性质是半可判定的：运行输入和，观察它是否在恰好消耗后停止。通过下半分接合枚举见证，计算均匀地在中。对于路径界限，固定一个输入和一个随机磁带：在上的单次确定性运行最多停机一次，因此“恰好停止消耗”的事件在上两两不相交，因此。

证明，半措施到机器：分配种子

给定，我们首先均匀有效地构造集合，使得

单元格被读取为的二元子区间，如记号部分所示，因此以下每个集合都是每个有限阶段半开二元区间的有限并集。一次处理一个的增量。

对于每个顶点，定义祖先和后代分配，并保持不变量：是从中继承的线性序的初始段。

不变量意味着和是一个共同有序集的初始段，因此嵌套，因此。从最深的占用顶点展开此递归，并利用，使顶点链上的集合在（6）下两两不相交，我们得到

假设下一个增量是字符串：分配到可用集合中最左边的测度集。空间足够：增加的近似仍服从路径预算，因此（7）给出;且是有效可计算的有限单元并，因为所有涉及的集合和长度都是二元的。

不相交性（6）保持，因为避免了所有与相当顶点的分配。不变量在四种情况下被检验：

在自身：在结束后，正好增长下一个可用测度，仍然是的初始段;
在严格的后代处：增长，且保持不变;初始段在包含它的任意子集中保持初始;
在的严格祖先处：增长且不变。每个可比较的顶点都可与比较，因此。因此，外点位于（旧不变量）之后，且可存在，也位于最左端之后。因此无间隙且为初始点;
在与不可比拟的顶点：则没有变化。

在所有阶段中，每个阶段均为一个有效的开测度集，均匀地在中，且（6）存活。

证明，半测量到机器：机器

定义机器：在当前消耗的输入前缀，它枚举——通过分接、在每个新前缀处重新开始，并每轮请求一个随机位——两个集合和的单元格相差（6）。

证书是一个枚举单元格，是消耗的随机字符串的前缀。如果的单元格被认证，则停止;如果的单元格被认证，它请求下一个输入位;如果这两个事件都未发生，则永远读取随机比特。

两个认证单元是的可比前缀，且圆柱相交，因此由于不相交，最多一种证书可以对给定发送。

固定字符串，一个扩展输入和一个随机磁带。设，即的某个单元格是的前缀。在每个处，我们有和，通过（6），：没有任何 -证书能触发（带有的证书会使用），而 -证书最终会触发——包含的单元格最终被枚举，最终成为增长的前缀。

因此机器走到，角色交换：，没有 -证书触发，只有某个 -证书触发，机器在恰好消耗输入后停止。反之，在停止显示证书，因此事件“stopts consuming exactly ”恰好是，且。

构造在的索引中是一致的。注意可能消耗的随机比特多于认证单元的长度;只有停机事件对重要，而非见证长度。∎

备注（确定性情形）。对于从不请求随机位的机器，是的指示器，是一个可计算枚举的反链。反过来，每个 c.e. 反链都是确定性实现的：在消耗的输入前缀处，枚举直到出现某个成员;如果，则停止，否则请求下一个输入位，重复（根据反链性质，则永久排除）。

因此，确定性停止机恰好实现了 -值的 l.s.c. 时间半测度，随机化将该类扩展到所有这些半测度。

上界

我们证明：每个都满足，其中是整数的普通前缀复杂度。（两边都是有限的：有些机器读取输入位并停止，因此对每个。）

对于整数，枚举且不重复集合;这在中有效且均匀，因为是半可计算的。每个输入路径的成员数都少于，因为。当它们被枚举时，我们赋予的等权重。

由于每条路径包含的数值少于它们，每条路径的预算小于。将这些增量输入前一子节的分配子。所有请求具有相同的二元权重，因此每个分配是一个深度单元：可用集合是有限个深度单元的补集，因此其最左端的测度部分是其最左边的单元。

写为分配给的单元格。

这是一种有效着色，在颜色下，可比字符串得到不同的颜色，它们的单元格相交（6）。因此，每个颜色类都是可计算枚举的反链，均匀地属于，上述注释的确定性过程恰好止于的成员，不消耗任何随机比特。

这种着色构造是由于 Vovk 和 Pavlovic 对定理10和18的证明。

一台停止机从其随机带读取一个自限程序计算（相对于固定的最优无前缀机），然后读取更多位，得到，并执行的过程。其在的见证正是字符串（程序），后接，因此给出，且对所有有一个常数<

参与讨论