跳转到导航 跳转到搜索 在算法信息论的计算机科学子领域中，柴廷常数（柴廷欧米茄数）[1] 或停机概率是一个实数，非正式地说，它表示随机构建的程序将停机的概率。这些数字是由 Gregory Chaitin 的结构形成的。尽管有无限多的停机概率，每种编码程序的方法都有一个，但通常使用字母 Ω 来表示它们，就好像只有一个一样。由于 Ω 取决于所使用的程序编码，因此有时在不指任何特定编码时称为 Chaitin 结构。每个停机概率都是一个不可计算的正常和超越实数，这意味着没有算法来计算它的数字。每个停止概率都是 Martin-Löf 随机的，这意味着甚至没有任何算法可以可靠地猜测其数字。停机概率的定义依赖于无前缀通用可计算函数的存在。这样的函数直观地代表了一种编程语言，它具有以下特性：无法获得有效程序作为另一个有效程序的适当扩展。假设 F 是一个偏函数，它接受一个参数，一个有限的二进制字符串，并可能返回一个二进制字符串作为输出。如果存在计算它的图灵机，则函数 F 被称为可计算的（从某种意义上说，对于任何有限二进制字符串 x 和 y，F(x) = y 当且仅当图灵机在给定时停止并在其磁带上显示 y输入 x)。如果以下性质成立，则函数 F 被称为通用函数：对于单个变量的每个可计算函数 f，都有一个字符串 w，使得对于所有 x，F( w x) = f( x)；这里 w x 表示两个字符串 w 和 x 的串联。这意味着 F 可用于模拟一个变量的任何可计算函数。非正式地，w 表示可计算函数 f 的“脚本”，F 表示“解释器”，它将脚本解析为其输入的前缀，然后在输入的其余部分执行它。 F 的域是定义它的所有输入 p 的集合。对于通用的 F，这样的 ap 通常既可以看作是程序部分和数据部分的串联，也可以看作是函数 F 的单个程序。
如果函数 F 的定义域中不存在两个元素 p, p' 使得 p' 是 p 的适当扩展，则函数 F 被称为无前缀。这可以重新表述为：F 的域是有限二进制字符串集合上的无前缀代码（瞬时代码）。强制无前缀的一种简单方法是使用输入方式为二进制流的机器，每次可以从中读取一个位。没有流结束标记；输入的结束由通用机器决定停止读取更多位的时间确定，其余位不被视为已接受字符串的一部分。到这里，上一段提到的两种程序概念的区别就很明显了；一种很容易被某种语法识别，而另一种则需要任意计算才能识别。任何通用可计算函数的域都是可计算可枚举集，但绝不是可计算集。域总是图灵等价于停机问题。设 PF 为无前缀通用可计算函数 F 的域。常数 Ω F 定义为 Ω F = ∑ p ∈ PF 2 − | p | {\displaystyle \Omega _{F}=\sum _{p\in P_{F}}2^{-|p|}} ，其中 | p | {\displaystyle \left|p\right|} 表示字符串 p 的长度。这是一个无限和，其中 F 域中的每个 p 都有一个被加数。域无前缀的要求以及 Kraft 不等式确保该和收敛到 0 到 1 之间的实数。如果 F 是从上下文中可以清楚地看出，Ω F 可以简单地表示为 Ω，尽管不同的无前缀通用可计算函数会导致不同的 Ω 值。知道 Ω 的前 N 位，就可以计算所有大小为 N 以内的程序的停机问题。设要解决停机问题的程序 p 为 N 位长。以燕尾的方式，所有长度的所有程序都运行，直到足够多的程序停止以共同贡献足够的概率来匹配这些前 N 位。如果程序 p 还没有停止，那么它永远不会停止，因为它对停止概率的贡献会影响前 N 位。因此，停机问题将解决 p。因为数论中的许多突出问题，例如哥德巴赫猜想，等价于解决特殊程序的停机问题（基本上就是寻找反例，找到就停机），所以知道足够的柴廷常数也意味着知道这些问题的答案。但是由于停机问题通常无法解决，因此除了 Chaitin 常数的前几位之外，不可能计算任何其他位，这只是将困难问题简化为不可能的问题，就像尝试为停机问题构建一个预言机一样。
康托空间是所有 0 和 1 的无限序列的集合。停机概率可以解释为在康托空间的通常概率测度下对康托空间的某个子集的测度。正是从这种解释中，停机概率才以它们的名字命名。康托空间上的概率测度，有时也称为公平硬币测度，被定义为对于任何二进制字符串 x，以 x 开头的序列集合的测度为 2 -| ×|。这意味着对于每个自然数 n，康托空间中满足 f(n) = 1 的序列集合 f 的测度为 1/2，第 n 个元素为 0 的序列集合也有测度 1/2。令 F 是一个无前缀的通用可计算函数。 F 的域 P 由无限组的二进制字符串 P = { p 1 , p 2 , ... } {\displaystyle P=\{p_{1},p_{2},\ldots \}} 组成。这些字符串 pi 中的每一个都确定了康托空间的子集 S i ；集合 S i 包含康托空间中所有以 p i 开头的序列。这些集合是不相交的，因为 P 是一个无前缀集合。总和 这样，Ω F 表示随机选择的无限 0 和 1 序列以 F 域中的位串（某些有限长度）开头的概率。 正是由于这个原因，Ω F 被称为一个停止概率。它在算法上是随机的（也称为 Martin-Löf 随机或 1-随机）。 [2] 这意味着输出Ω的前n位的最短程序的大小必须至少为nO(1)。这是因为，就像在哥德巴赫的例子中一样，这 n 位使我们能够准确地找出所有长度最多为 n 的程序中哪些程序停止。
因此，它是一个正常数字，这意味着它的数字是均匀分布的，就好像它们是通过抛硬币产生的一样。它不是一个可计算的数字；没有可计算的函数来枚举其二进制扩展，如下所述。使得 q < Ω 的有理数集 q 是可计算可枚举的； [3]具有这种性质的实数在递归理论中称为左-ce实数。使得 q > Ω 的有理数集 q 不可计算枚举。 （原因：每个具有此性质的左实数都是可计算的，而 Ω 不可计算。）图灵等价于停机问题，因此在水平 Δ 2 0 {\displaystyle \Delta _{2}^{0}}算术层次结构。并非所有图灵等价于停机问题的集合都是停机概率。一个更精细的等价关系，Solovay 等价，可用于刻画 left-ce 实数之间的停止概率。 [4] 可以证明 [0,1] 中的实数是 Chaitin 常数（即某些无前缀的通用可计算函数的停机概率）当且仅当它是 left-ce 并且在算法上是随机的。 [4] Ω 是少数可定义的算法随机数之一，也是最著名的算法随机数，但它根本不是所有算法随机数的典型代表。 [5] 如果存在一种算法，该算法在给定 n 时返回该数的前 n 位数字，则该实数称为可计算的。这相当于存在一个枚举实数数字的程序。
没有停止概率是可计算的。这一事实的证明依赖于一种算法，该算法给定 Ω 的前 n 位数字，解决了长度为 n 的程序的图灵停机问题。由于停机问题是不可判定的，因此无法计算 Ω。该算法如下进行。给定 Ω 的前 n 位数字且 ak ≤ n，算法将枚举 F 的域，直到找到足够的域元素，使它们表示的概率在 Ω 的 2 -( k+1) 范围内。在这一点之后，域中不能再有长度为 k 的程序，因为每个程序都会为度量增加 2 − k，这是不可能的。因此，域中长度为 k 的字符串集合正是已经枚举的此类字符串的集合。如果表示实数的二进制序列是算法上的随机序列，则实数是随机的。 Calude、Hertling、Khoussainov 和 Wang 证明 [6] 递归可枚举实数是算法上的随机序列，当且仅当它是 Chaitin Ω 数。对于自然数的每个特定一致有效表示的公理系统，例如 Peano 算术，都存在一个常数 N，使得在该系统内，第 N 个之后的 Ω 位不能被证明是 1 或 0。常数 N 取决于形式系统如何有效表示，因此不直接反映公理系统的复杂性。这个不完备性结果类似于哥德尔不完备性定理，因为它表明没有一致的算术形式理论是完备的。如上所述，Gregory Chaitin 常数 Ω 的前 n 位是随机的或不可压缩的，因为我们无法通过少于 nO(1) 位的停机算法来计算它们。但是，请考虑系统地列出并运行所有可能的程序的简短但永不停止的算法；每当其中一个停止时，它的概率就会被添加到输出中（初始化为零）。在有限的时间之后，输出的前 n 位将永远不会再改变（这个时间本身不能被停止的程序计算，这无关紧要）。所以有一个简短的非停止算法，其输出收敛（在有限时间之后）到 Ω 的前 n 位。换句话说，Ω 的可枚举的前 n 位是高度可压缩的，因为它们可以通过非常短的算法进行极限计算；对于枚举算法集，它们不是随机的。 Jürgen Schmidhuber (2000) 构建了一个极限可计算的“超级 Ω”，它在某种意义上比原始的极限可计算 Ω 更随机，因为人们无法通过任何枚举非停机算法显着压缩超级 Ω。对于另一种“超级Ω”，无前缀通用图灵机（UTM）的普遍性概率——即，即使它的每个输入（作为二进制字符串）都以随机二进制字符串为前缀，它仍然保持普遍性的概率– 可以看作是机器的非停机概率，oracle 是停机问题的第三次迭代（即 O ( 3 ) {\displaystyle O^{(3)}} 使用图灵跳跃表示法）。 [7] ^ Calude、Hertling、Khoussainov 和Wang：递归可枚举实数和Chaitin 的Ω 数。理论计算机科学 255:125–149, (2001) http://webpages.uncc.edu/yonwang/papers/TCS01.pdf
^ Barmpalias, G. 和 Dowe DL (2012)。 “无前缀机器的普遍概率”。 Philosophical Transactions of the Royal Society A. 370 (1): 3488–3511（主题问题“计算、物理学和思维的基础：图灵遗产”由 Barry Cooper 和 Samson Abramsky 编译和编辑）。 doi：10.1098/rsta.2011.0319。 PMID 22711870。Cristian S. Calude (2002)。信息和随机性：算法视角，第二版。斯普林格。 ISBN 3-540-43466-6 Ming Li 和 Paul Vitányi (1997)。 Kolmogorov 复杂性及其应用简介。斯普林格。介绍章节全文。 Jürgen Schmidhuber (2000)。万物算法理论（arXiv：quant-ph/ 0011122）。期刊参考：J. Schmidhuber (2002)。广义 Kolmogorov 复杂性的层次结构和在极限中可计算的不可数的通用度量。国际计算机科学基础杂志 13(4):587-612。 Chaitin 的 Omega 调查文章的各个方面讨论了 Chaitin 的 Omega 研究的最新进展。 Omega 以及为什么数学没有 TOE 文章基于 Gregory Chaitin 撰写的一篇文章，该文章发表在 2004 年 8 月版的《今日数学》中，在艾伦·图灵逝世 50 周年之际。极限可计算的超级欧米茄比欧米茄更随机和算法信息的概括，作者：Jürgen Schmidhuber