柴廷常數

在计算机科学的算法信息论中，柴廷常数（也称柴廷欧米茄数）或任意随机图灵机停机的概率是一个实数。即，柴廷常数代表着随机生成的程序在通用图灵机上最终将会停机的概率。这一数字被格雷戈里·柴廷所构造。

即便有无穷多个最终停机的概率（存在无穷多个针对特定图灵机的停机概率常数），我们使用字母 \Omega 表示特定的前缀无符号通用图灵机最终停机的概率的统称。由于 \Omega 取决于图灵机具体编码的细节，因此在不指代任何特定图灵机的编码方式时，它常被称为柴廷構造而非柴廷常数。

每个图灵机所停机的概率是一个正规且超越的实数，且这一概率并不是可计算数。因为每个特定图灵机所停机的概率是马丁-洛夫随机的，没有算法可以用于计算它的实际位数。

背景
停机概率的定义基于前缀无符号通用可计算函数的存在。直观地说，这种函数代表了一种特殊的编程语言，即其中没有任何合法的程序代码是另一个合法程序的前缀（即不存在一个有效程序可以通过在另一个有效程序末尾添加字符得到）。

设 F为一个接受有限二进制字符串作为参数、且可能输出单个二进制字符串的偏函数。若存在任意一个图灵机可以计算该函数，则这个函数F被称为可计算的。具体来说，对于任何有限的二进制字符串x和y，当且仅当该图灵机在以x作为输入时最终停机，且最终磁带上的内容为y。

如果对于每一个单变量的可计算函数 f 都存在一个字符串 w 使得对于所有 x 都有 F(w,x)=f(x)，那么函数 F 就被称为计算通用的，其中 w,x 表示两个字符串 w 和 x 的串接。这意味着 F 可用于模拟任何单变量可计算函数。换句话说，w 代表可计算函数 f 的一段“脚本”，而 F 则代表一个“解释器”，它将脚本解析为其输入的前缀，然后在输入的剩余部分上执行它。

F 的定义域是使其有定义的所有输入 p 的集合。对于通用的 F，这样的 p 通常既可以看作程序部分和数据部分的连接，也可以看作函数 F 的单个程序。

如果函数 F 的定义域中不存在两个元素 p、p'，使得 p' 是 p 的真扩展，则称 F 是无前缀的。这可以重新表述为：F 的定义域是有限二进制字符串集合上的一个前置碼（即时码）。一种强制无前缀性的简单方法是使用以二进制流作为输入方式的机器，比特位可以被逐位读取。这里没有流结束标记；输入的结束由通用机器决定何时停止读取更多比特来确定，而剩余的比特不被视为已接受字符串的一部分。在此，上段提到的两种程序概念之间的区别就变得清晰了：一种很容易被某种形式语法识别，而另一种则需要任意计算才能识别。

任何通用可计算函数的定义域都是一个递归可枚举集合，但并不是递归可计算的。它的定义域在不可解度上等价于停机问题。

定义
设P_F是无字首的图灵完备的可计算函数F的定义域，常数\Omega_F被定义为

: \Omega_F = \sum_{p \in P_F} 2^{-|p|},

\left|p\right| 表示的字串p的长度。这是一个无限和， 其中有一个加数对於F的定义域中的每個p。这要求该定义域是无字首的，再配合克拉夫特不等式，确保这个和会收敛到0到1之间的一个实数。如果F是明確的，则\Omega_F可以被简单地写为\Omega，虽然不同的无字首的图灵完备的可计算函数会有不同的\Omega值。

与停机问题的关系
知道\Omega的（二进制的）前N位数，我们可以计算出每个不超过N个字元的程式的 停机问题 。假设程式p其停机问题是要解决N个字元的程式。在衔接时，所有长度的所有程式都在运行，直到足够的程式贡献了足够的机率，以与这些「前N位数」相配。如果程式p并没有停止，那么它永远也不会，因为它的贡献停止的概率将影响的第N位。因此，制止的问题（对於p）将得到解决。

因为有很多悬而未决的数论问题，例如哥德巴赫猜想，相当于解决特别程式（这基本上就是搜索反例，如果有一个反例发现就停止）的停机问题，知道了柴廷常数的足够位数还将意味着知道这些问题的答案。但是，由於停机问题一般並不是可以解决的，因此计算柴廷常数的任意位数是不可能的，这只是把困难的问题变成不可解決的问题，就像在试图建立一个預言机一樣。

解释作为一个机率
康托空间是所有0跟1的无限序列的集合，一个停机的概率可被解释为的测度的特定子集的康托空间在通常的概率衡量在康托空间。它是从这一解释，终止的概率取他们的名字。

该概率的测度在康托空间，有时也称为公平的硬币措施，定义，以便为任何二元字串x的组序列的开头x具有测量2^{-\left \vert x \right \vert}. 这意味着为每个自然的数量n，该组序列的f在坎特的空间，这样 f(n)=1测量的\frac{1}{2}和本组序列的n个元素是0还有衡量的\frac{1}{2}。

设F是无字首的图灵完备的的可计算函数，F的定义域P包括一个二元字串的无限集合

: P = \{p_1,p_2,\ldots\}.

这些字符串中的每一个pi確定了康托空间的一个子集Si， 该组Si包含康托空间的所有從pi开始的序列。这些都是分离的，因为P为无字首的集合， 总和

: \sum_{p \in P} 2^{-|p|}

表示该集合的测度

: \bigcup_{i \in \mathbb{N}} S_i.

在这种方式， \Omega_F表示的概率是随机选择的无限的0跟1的序列以F的定义域裡的一位字串（的某个有限的长度）開始，由于这个原因，\Omega_F被称为停机的概率。

性質
每个柴廷常数 \Omega 具有以下性質：

• 是算法随机的（也称为马丁-洛夫随机或 1-随机）。这意味着，要确定 \Omega 的前 n 位二进制展开，任何程序都必须使用至少 (n - O(1)) 位的信息。直观地说，\Omega 的前 n 位包含了关于所有长度不超过 n 的程序是否停机的不可压缩信息。例如，利用这些位可以判定哪些长度至多为 n 的无前缀程序会停机。
• 它是一个正规数。即在其二进制展开中，每一位（0或1）出现的频率趋于相等，整体表现为“如同反复抛掷一枚公平的硬币”生成。
• 它不是一个可计算数。不存在图灵机能够逐位列出其完整的二进制展开，如下文所讨论的。
• 它具有左递归可枚举性。集合 ({q \in \mathbb{Q} \mid q 是递归可枚举的。在递归论中，具有此性质的实数被称为 左递归可枚举的实数。但它不是右递归可枚举的。集合 ({ q \in \mathbb{Q} \mid q > \Omega }) 不是递归可枚举的。若一个实数既是左递归可枚举又是右递归可枚举的（即其上下逼近均可枚举），则它必为可计算数；但 \Omega 不可计算，故其上界集不可枚举。
• 它是一个算术数。
• 它在不可解度上等价于于停机问题，因此属于算术阶层的第\Delta^0_2阶。

但并非所有图灵等价于停机问题的实数都是柴廷常数。通过一种称为 索洛维等同的等价关系，可以在左递归可枚举的实数中描述哪些是真正的停机概率。当且仅当一个实数既是左递归可枚举的，又是算法随机的，这一实数 (\alpha \in [0,1])才属于某个无前缀通用图灵机的柴廷常数。

尽管 \Omega 是少数几个明确可定义的算法随机数中最著名的例子之一，但它在算法随机数的全体中并不“典型”，因为大多数算法随机数甚至是不可定义的。

不可计算性
一个实数是可计算的，如果有一个算法，给出n，返回该数的前n个位数。 这相当于存在一个程式，能夠列举数字的所有位数。

没有停机的概率是可计算的。 证明这一事实依赖于一种算法，给出\Omega的前n个位数，解决图灵的停机问题对於长度不超過n的程式。由于停机问题是不可判定问題，\Omega沒有办法被计算出來。

算法进行如下。 给出 \Omega 的前n个位数，以及数字k\leq n，这个算法枚举了F的定义域，直到这个定义域裡足够的元素已经被找到，使他们所代表的概率是\Omega的2^{-(k+1)}. 在这一点后，没有长度k的附加程式可以在定义域裡，因为每个程式将增加2^{-k}到这个措施，这是不可能的。因此，长度k的字串的集合在这个定义域中就是「已经一一列举的字串的集合」。

算法随机性
若表示某个实数的二进制序列属于算法随机序列，则称这个实数是“随机的”。Calude、Hertling、Khoussainov与Wang证明了，当且仅当一个递归可枚举实数是某个特定图灵机的蔡廷\Omega常数，它才是算法随机的。

柴廷数
柴廷常數是指停機的概率，通常不是可計算數，且有無窮多個停止的概率（每個方法的程式編碼都各有一個）。其中一種通用圖靈機的停機概率\Omega_U由卡盧德（Calude）等人計算並給出數值，約為0.007875：
:\Omega_U \approx \,0.00787499699...

停机问題的不完备定理
对于每个一致且可以表示自然数的公理系统（如皮亚诺公理）而言，都存在一个常数N使得该系统中\Omega的二进制表示中第N位后的任何位都不能被证明为1或0。这个常数N取决于该形式系统的有效表示方式，因而并不能反映公理系统本身的复杂性。这一不完备性的结果与哥德尔不完备定理类似，均表明任何一致的算术形式理论都不是完备的。

参见

• 不完备定理
• 柯氏复杂性

参考文献