柴廷常数
目录
柴廷常数
在算法信息论的计算机科学子领域中，Chaitin 常数（Chaitin 欧米茄数）或停机概率是一个实数，通俗地说，它表示随机构建的程序停机的概率。 这些数字是根据 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，这样的 p 通常可以看作既是程序部分和数据部分的串联，又是函数 F 的单个程序。
如果函数 F 的定义域中没有两个元素 p、p’ 使得 p’ 是 p 的适当扩展，则函数 F 称为无前缀。 这可以改写为：F 的域是有限二进制串集合上的无前缀代码（瞬时代码）。 强制无前缀性的一种简单方法是使用输入方式为二进制流的机器，一次可以从中读取一个位。 没有流结束标记； 输入结束由通用机器决定停止读取更多位的时间决定，其余位不被视为接受字符串的一部分。 在这里，上一段中提到的两个程序概念之间的区别变得很清楚了； 一个很容易被一些语法识别，而另一个需要任意计算才能识别。
任何通用可计算函数的域都是可计算可枚举集，但绝不是可计算集。 域总是图灵等价于停机问题。
定义
令 PF 为无前缀通用可计算函数 F 的定义域。常数 ΩF 定义为
Ω F = ∑ p ∈ P F 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 的停机问题将得到解决。
因为数论中很多悬而未决的问题，比如哥德巴赫猜想，相当于解决特殊程序的停机问题（基本上就是找反例，找到就停机），知道柴廷常数就够了 也意味着知道这些问题的答案。