柴廷常數

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

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

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

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

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

函数被称为图灵完备，如果拥有下列性質：对于一个单一的变量的每个可计算函数 ，都有一串使得对於所有的, ；这里   表示两个二元串和的串接. 这意味着：可用于模拟一个变量的任何一个可计算函数。非正式地说，表示可计算函数的「腳本」，另外表示一个"解释"解析脚本作为前缀的其输入和随后执行它其余的输入。

的定义域是所有输入的集合。对于图灵完备的，这样的通常可以被看到作为程式部分和数据部分的连接，并作为函数的单一程式。

函数被称为无字首如果没有两个元素 , 在其定义域使得是的一个部分扩展，換句話說，的定义域是一个前置码（瞬间代码）在有限二元串的集合。一个简单的方法來强制执行「无字首性」是使用机器，这些机器的输入是一个二流从哪位可以读一个在一段时间。 没有结束的标记；结束的输入确定通过时这个图灵完备的机器决定将停止阅读更多位数。在这里，之间的差别这两个概念的程序中提到的最后一段变得清楚的；一个是很容易地认识到一些文法，而其他需要任意的计算到承认。

任何图灵完备的可计算函数的定义域都是递归可枚举集合，但是不是递归集合. 这个定义域是图灵等同于停机问题.

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

 ,

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

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

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

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

该概率的测度在康托空间，有时也称为公平的硬币措施，定义，以便为任何二元字串的组序列的开头具有测量. 这意味着为每个自然的数量，该组序列的在坎特的空间，这样 测量的和本组序列的个元素是0还有衡量的。

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

 .

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



表示该集合的测度

 .

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

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

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

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

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

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

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

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

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

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

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

 参见 

 不完备定理
 柯氏复杂性

参考文献

Category:算法信息论
Category:計算理論
Category:实数超越数