形式陈述
前缀机、通用机与最短描述
前缀机是一个从有限二进制串到有限二进制串的部分可计算函数 理路 部分可计算函数 Partial computable function 允许机器在函数未定义的输入上不停机的部分函数。 M ,要求停机程序集合 dom ( M ) 前缀自由 理路 前缀码 Prefix-free code 码字互不为前缀并保留单射源标签的编码;正码长时可即时译码。 :其中任何两个不同程序都不互为前缀。输出串集合不受此前缀条件限制。
存在一台通用前缀机 U ,使每台前缀机 M 都有常数 d M ,满足
K U ( σ ) ≤ K M ( σ ) + d M , K M ( σ ) = min { | p | : M ( p ) = σ } . 没有程序输出 σ 时,右侧最小值记为 + ∞ 。通用机能输出每个有限串,故 K U 总为有限整数。固定这样一台 U ,简写 K = K U ,称为前缀 Kolmogorov 复杂度 。更换通用前缀机只会令所有字符串的 K 改变一个统一加法常数。[1]
有效编码定理与随机性刻画
Kraft–Chaitin 定理。 设程序逐个枚举请求 ( n i , σ i ) ,其中 n i 是非负整数;请求可以有限或无限,重复出现也要重复计算权重。若
∑ i 2 − n i ≤ 1 , 就可以有效地给每个请求分配不同程序 p i ,使所有 p i 前缀自由、| p i | = n i ,并构造一台前缀机 M 满足 M ( p i ) = σ i 。于是对某个只依赖整台 M 的常数 d ,每个请求都有
(1) K ( σ i ) ≤ n i + d . Levin–Schnorr 定理。 在公平币测度下,无限二进制序列 X 是 Martin-Löf 随机 理路 Martin-Löf 随机性 Martin-Löf randomness · 马丁–勒夫随机性 以统一可枚举、概率预算趋于零的开集检验,定义单条无限比特序列的随机性,并构造通用检验。 ,当且仅当
(2) ∃ c ∈ N ∀ n ≥ 0 K ( X ↾ n ) ≥ n − c . 也就是说,所有有限前缀的压缩亏损 n − K ( X ↾ n ) 有同一个常数上界。常数可以依赖 X 与通用机,不能随 n 任意增大。下面给出编码定理和式 (2) 的双向证明。[1]
直觉
短程序占用一块较大的码树空间:长度 r 的程序占用权重 2 − r 。前缀条件使这些空间互不重叠,Kraft 不等式 理路 Kraft–McMillan 不等式 Kraft–McMillan inequality 刻画给定码长集合存在前缀码或唯一可译码的必要充分不等式。 便把“有多少短描述”转成概率预算。如果一个长度 n 的前缀只需 n − c 位描述,它所确定的柱集可以放进总质量至多 2 − c 的有效异常集合。
反方向则把检验看成压缩资源。第 2 k 层最多占 2 − 2 k 的质量;若把这一层每个柱集的描述缩短 k 位,总代价至多 2 − k 。所有 k ≥ 1 层的代价加起来仍不超过一,可以装进同一台前缀机。被检验每层捕获的序列因此具有亏损越来越大的前缀。
先构造通用前缀机
按有效编号 理路 程序编号与可接受编号 Program indexing · Acceptable numbering · Gödel numbering 对部分可计算函数进行有效枚举,并要求编号支持通用解释与有效参数编译。 枚举所有部分可计算函数的程序,并交错模拟每个程序在所有有限输入上的计算。对固定编号 e ,每当观察到一个新停机输入 p ,只在它与此前已接受的输入都无前缀关系时接受这次输入及其输出;重复事件忽略。检查只涉及有限个已接受输入,因而有效。
所得机器 M e 的定义域总前缀自由。如果原函数本来就是前缀机,过滤不会丢掉任何停机输入,因此 ( M e ) 仍包含所有前缀机。这是在枚举时保证性质,不需要判定任意程序是否具有该性质。
用前缀自由的编号标记 1 e 0 ,定义
U ( 1 e 0 p ) = M e ( p ) . 不同编号的标记互不为前缀;同一编号内则由 M e 的定义域保证前缀自由。于是 U 是前缀机,并有 K U ( σ ) ≤ K M e ( σ ) + e + 1 。对每个有限串,都存在只在一个指定程序上输出它的前缀机,所以 U 的最短描述总存在。
Kraft–Chaitin:请求到来时就分配码字
维护已分配程序集合 A 和有限的空闲串集合 F ,初始为 A = ∅ 、F = { ε } 。保持两个不变量:A ∪ F 的柱集两两不交且覆盖全部无限序列;F 在每种长度上至多有一个串。
收到长度 n 的请求时,在满足 | z | ≤ n 的空闲串中选择最长 的 z 。分配
p = z 0 n − | z | , 从 F 删除 z ,并加入沿这条零分支留下的兄弟节点
z 1 , z 01 , … , z 0 n − | z | − 1 1. 若 | z | = n ,直接分配 z ,不加入兄弟节点。这些新空闲柱集与 [ p ] 恰好分割原来的 [ z ] ,所以第一个不变量保持。因为选的是最长可用 z ,此前不存在长度在 | z | + 1 , … , n 的空闲串,故第二个不变量也保持。
为何总找得到 z ?分配当前请求之前,已用预算加上 2 − n 至多为一,故空闲质量至少是 2 − n 。若每个空闲串长度都大于 n ,由于空闲集有限、每个长度至多一个,就有
∑ z ∈ F 2 − | z | < ∑ j > n 2 − j = 2 − n , 矛盾。算法因此可逐项完成,不必预知未来请求,也不用把无限请求按长度排序。
机器 M 在输入 p 上模拟请求枚举与上述分配;一旦 p 被分给请求 ( n , σ ) ,就输出 σ ,否则继续等待。这定义部分可计算函数,其停机域正是前缀自由的已分配程序集合。用通用性的同一个常数 d M 即得式 (1)。有限阶段前缀自由还保证无限极限中的任意两码字不冲突。
有效开集如何得到不可撤回的前缀自由枚举
Levin–Schnorr 的反方向需要把有效开集 V 写成
V = ⋃ σ ∈ P [ σ ] , μ ( V ) = ∑ σ ∈ P 2 − | σ | , 其中 P 本身可以枚举且前缀自由。不能先输出较长串,再在较短前缀出现时撤回旧输出;前缀机已经分配的程序也不能这样反悔。
具体做法是维护当前已输出的有限前缀自由集合 B 。原枚举器输出 τ 时,取 L 为 | τ | 与 B 中最大长度的最大值,若 B 为空就取 L = | τ | 。枚举 τ 的所有长度 L 延伸,仅输出那些没有 B 中任何串作为前缀的延伸。
这些新柱集恰好组成 [ τ ] 减去已经输出的并集;它们彼此不交,也与旧柱集不交。因此每一步保持相同的已覆盖开集,并且从不撤回输出。这个有限操作可计算,对带层号的枚举交错执行即可保持统一有效性。所有阶段输出的并集 P 就是所求表示。[2]
Levin–Schnorr 的两个方向
随机序列没有无界压缩亏损
对每个整数 c ≥ 0 ,定义
R c = ⋃ { [ σ ] : ∃ p ( U ( p ) = σ ∧ | p | ≤ | σ | − c ) } . 交错运行所有程序,观察停机输出,即可统一枚举这些开集;完全不必计算哪个程序最短。为了估计质量,在数学上为每个输出串 σ 选一个最短程序 p σ 。不同输出对应不同程序,而这些程序都在 U 的前缀自由定义域内,所以可数前缀集合的 Kraft 必要性 理路 Kraft–McMillan 不等式 Kraft–McMillan inequality 刻画给定码长集合存在前缀码或唯一可译码的必要充分不等式。 给出
∑ σ 2 − K ( σ ) ≤ 1. 对构成 R c 的串,K ( σ ) ≤ | σ | − c ,故由柱集的并集界 理路 并集界 Union bound · Boole 不等式 多个坏事件中至少一个发生的概率,不超过各事件概率之和。
(3) μ ( R c ) ≤ ∑ K ( σ ) ≤ | σ | − c 2 − | σ | ≤ 2 − c ∑ σ 2 − K ( σ ) ≤ 2 − c . 于是 ( R c ) 是合法 Martin-Löf 检验。若 X 随机,它不在某层 R c ,所以每个前缀都满足 K ( X ↾ n ) > n − c ,从而满足式 (2)。此处选择最短程序只用于质量证明,没有把这种选择当成一个可执行步骤。
失败于有效检验会产生无界亏损
反设 X 非随机,有合法检验 ( V m ) 使 X ∈ V m 对每个 m 成立。对每个 k ≥ 1 ,用上面的不可撤回转换把 V 2 k 表示为前缀自由的统一可枚举集合 P k 。
每当 σ 在第 k 个集合被列出,就枚举一个请求
( | σ | − k , σ ) . 因为 [ σ ] ⊆ V 2 k ,有 2 − | σ | ≤ 2 − 2 k ,故 | σ | ≥ 2 k ,请求长度确实非负。所有层放进同一个请求枚举器,总权重是
(4) ∑ k ≥ 1 ∑ σ ∈ P k 2 − ( | σ | − k ) = ∑ k ≥ 1 2 k μ ( V 2 k ) ≤ ∑ k ≥ 1 2 − k = 1. 同一个串若在多个层出现,每次都计费;式 (4) 已经包括这些重复。Kraft–Chaitin 定理构造一台机器,通用性再给一个独立于 k , σ 的常数 d ,使每个请求满足
K ( σ ) ≤ | σ | − k + d . X ∈ V 2 k 保证有某个前缀 σ k ∈ P k 。于是 | σ k | − K ( σ k ) ≥ k − d ,随 k 无界,违反式 (2)。这完成逆否证明,也闭合了两个方向。
例子与边界
乱序码长仍可在线分配
依次请求 ( 3 , 00 ) , ( 3 , 01 ) , ( 1 , 10 ) , ( 2 , 11 ) 。总权重为 1 / 8 + 1 / 8 + 1 / 2 + 1 / 4 = 1 ;码长不是递增的。
请求长度与输出
分配的程序
分配后空闲串
初始
—
ε
( 3 , 00 )
000
1, 01, 001
( 3 , 01 )
001
1, 01
( 1 , 10 )
1
01
( 2 , 11 )
01
无
程序 1 虽然到第三步才出现,先前一直为它保留着完整子树。若第一步任意选取空闲空间并打碎这棵子树,单有剩余总质量并不自动保证后续短码字可分配;每个长度至多一块空闲空间的不变量正避免这种碎片化。
再看开集枚举:原程序先输出 000,再输出 00。不可撤回转换先输出 000,第二次只补上 001,得到前缀自由集合 { 000 , 001 } ,质量 1 / 4 ,其柱集并恰为 [ 00 ] 。只删除旧串再写 00 虽可维护一个有限显示列表,却不能作为此前编码程序的枚举过程。
一个具体检验如何变成压缩请求
令 V m = [ 0 m ] ,则 μ ( V m ) = 2 − m ,并且 0 ∞ 落在每一层。第 2 k 层只有串 0 2 k ,因此上面的构造请求长度为 k ,输出为 0 2 k 。权重 ∑ k ≥ 1 2 − k = 1 ,得到
K ( 0 2 k ) ≤ k + d , 2 k − K ( 0 2 k ) ≥ k − d . 它直接展示了非随机序列的无界亏损。这个界无需最优压缩:例如专门编码长度还可能更短,但当前构造已经足以否定式 (2)。
不能省略的约束
前缀自由要求落在程序域 。把它删掉,就不能对最短程序直接使用式 (3) 的 Kraft 总预算,因而不能把式 (2) 原样换成任意普通机器的最短输入长度。反方向也没有为每个可能前缀长度都申请一个短程序;请求来自每层的互不相交柱集表示,并且用稀疏层 2 k 使总预算可和。
定理是关于一条无限序列的全部前缀。单个长串恰好难压缩,或在有限测试中没有发现压缩方法,都没有验证这个无限量词。证明只构造停机事件的枚举,不提供总能认证 K ( σ ) 精确值的程序。
推论与应用
若通用机改为 U ′ ,模拟关系双向给出 | K U ( σ ) − K U ′ ( σ ) | ≤ d ,所以常数亏损条件保持不变。序列的具体亏损常数依赖描述语言,随机序列这一集合则不依赖通用前缀机的选择。
开集检验与压缩描述给出同一随机性的两种入口:式 (3) 把短描述变成合法检验,式 (4) 把检验失败变成同一台机器中的一系列压缩见证。结合 Martin-Löf 随机序列具有测度一,可知满足统一亏损界的序列存在且几乎处处成立;这不是通过穷举计算最短程序来找出某条具体随机序列。
把所有输出同一字符串的停机程序权重相加,得到离散下半可计算半测度 理路 下半可计算半测度 Lower semicomputable semimeasure 在可数输出上用总质量不超过一的下半可计算权重描述部分程序,并区分离散半测度和前缀树半测度。 。它补充本页最短程序的视角:多条较长描述也能累积质量,而缺失质量来自没有终止输出的输入;后续编码定理把总质量重新连接到最短描述长度。
单元终结任务:把概率预算换成描述长度
一个候选检验的第 2 层依次列出 00、000、01。按通用检验的修整规则,哪些输出被接受?每一步算柱集的并,比较直接把三次输出的权重相加会错在哪里。再把原始开集枚举 000、00 转成不可撤回的前缀自由枚举,列出第二步实际新增的串。
从空码树出发,执行请求 ( 3 , 00 ) , ( 3 , 01 ) , ( 1 , 10 ) , ( 2 , 11 ) ,逐步列出已分配程序与空闲串。核对两个不变量,然后追加一个长度 4 的请求:此时失败的是算法的正确性,还是输入的预算承诺?另从空码树单独请求长度 0 ,应分到什么,之后还能接受其他请求吗?
对 V m = [ 0 m ] ,把第 2 k 层变成请求。算 k = 1 , 2 , 3 的请求、共同预算及余下全部层的预算;若改用第 k 层而仍缩短 k 位,会发生什么?说明为何所有请求必须交给同一台机器,并区分“重复输出同一柱集”与“重复提交同一码长请求”的计费。
不依赖前面有限算例,分别说明短程序怎样产生合法检验,以及检验失败怎样产生无界压缩亏损。最后判断两句话:“对每个长度各有一个压缩常数,就满足随机性刻画”;“某个前缀很难压缩,所以已认证整条序列随机”。分别指出量词或有限观察的问题,并为任意指定前缀解释两种随机性不同的无限延续为何都存在。
核对:第一题接受 00、000,并质量始终为 1 / 4 ;01 会把并增到 1 / 2 ,故丢弃。原三输出的权重和为 5 / 8 ,既重复计了 [000],也包含被丢弃的输出。不可撤回转换先保留 000,第二步只新增 001,两柱集恰好覆盖 [00]。第二题依次分配 000、001、1、01;空闲集依次为 { 1 , 01 , 001 } 、{ 1 , 01 } 、{ 01 } 、空集。预算已达一,追加请求使它成为 17 / 16 ,超出定理前提;单独的零长请求取得 ε ,同样用尽全部容量。
第三题请求为 ( 1 , 00 ) , ( 2 , 0000 ) , ( 3 , 000000 ) ,预算合计 7 / 8 ,余下为 1 / 8 。若改取第 k 层,则每次都请求长度零,权重全为一,无穷总预算发散。共同机器给出一个不依赖层号的模拟常数 d ,从而亏损至少 k − d ;各层各自的常数若随 k 增长,就不能推出无界亏损。柱集重复不增加集合质量,重复请求却分别占用不同程序,必须每次计费。第四题分别使用式 (3) 的 Kraft 与并集界、式 (4) 的共同请求预算和在线编码;前者不能执行“找最短程序”,后者不能撤回旧码字。随机性要求同一个常数控制所有长度。任意有限前缀都有接全零的可计算延续,也有随机延续:该柱集质量为正,而全部非随机序列仅占零测集。
参考资料