柴廷常数

在计算机科学中的算法信息论，柴廷常数（柴廷欧米茄数）^[1]或停机的概率是一个实数，非正式地来讲，所表示的是随机的程式将会停止的概率。这些数字是从一个格雷戈里·柴廷制作的构造。

尽管有无穷多个停止的概率（每个方法的程式编码都各有一个），使用字母 ${\displaystyle \Omega }$ 代表他们是很普通的。因为 ${\displaystyle \Omega }$ 取决于程序编码使用的程式，这有时被称为柴廷构造，而不是柴廷常数当没有参考任何特定的编码的时候。

每个停止的概率是一个正规数和超越数的实数，而不是可计算数，这意味着，没有算法计算他的位数。事实上，每个停止的概率是马丁-洛夫随机的，意味着甚至没有任何的算法是可以可靠地猜测他的位数的。

背景

停止的概率的定义依赖于无字首的图灵完备的可计算函数的存在。这样的函数，直观地说，代表了一种编程语言具有这样的性质：没有有效的程式可以被获得为另一个有效的程式的部分扩展。

假设 ${\displaystyle F}$是一个部分函数，需要一个参数跟一个有限的二元串，并有可能返回一个二元串作为输出。这个函数${\displaystyle F}$被称为可计算的，如果有一个图灵机有计算出他(在这个意义上：对于任何有限的二元串${\displaystyle x}$和${\displaystyle y}$、${\displaystyle F(x)=y}$ 当且仅当这个图灵机停止且${\displaystyle y}$在他的地带当给出输入${\displaystyle x}$的时候).

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

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

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

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

定义

设${\displaystyle P_{F}}$是无字首的图灵完备的可计算函数${\displaystyle F}$的定义域，常数${\displaystyle \Omega _{F}}$被定义为

${\displaystyle \Omega _{F}=\sum _{p\in P_{F}}2^{-|p|}}$,

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

与停机问题的关系

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

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

解释作为一个机率

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

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

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

${\displaystyle P=\{p_{1},p_{2},\ldots \}}$.

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

${\displaystyle \sum _{p\in P}2^{-|p|}}$

表示该集合的测度

${\displaystyle \bigcup _{i\in \mathbb {N} }S_{i}}$.

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

性质

每个柴廷常数 ${\displaystyle \Omega }$ 具有以下性质：

• 它是算法随机（也称为马丁-洛夫随机或1-随机）。^[2] 这意味着！最短的程式输出的第 ${\displaystyle n}$ 位的 ${\displaystyle \Omega }$ 必须的时间至少为 n-O(1)。 这是因为，作为在哥德巴赫的例子，这些 ${\displaystyle n}$ 位数使我们能够找出到底哪些最多${\displaystyle n}$个字元的程式将会停止。
• 它是一个正规数，这意味着，其位数出现机率都一样，就如同他们是用“扔一个公正的硬币”来产生的。
• 它不是一个可计算数；没有可计算的函数能计算出它的值、列举它的二进制的所有位数，如下文所讨论的。
• “有理数${\displaystyle q}$使得的 ${\displaystyle q<\Omega }$”的集合是递归可枚举集合;^[3] 在递归理论，一个有这种性质的实数称为 左-c。e. 实数 .
• “有理数${\displaystyle q}$使得${\displaystyle q>\Omega }$”的集合不是递归可枚举的。 (原因是：每一个有这种性质的左-c。e. 实数都是可计算的，但是这个 ${\displaystyle \Omega }$ 并不是。)
• ${\displaystyle \Omega }$ 是一个 算术数.
• 这是图灵等同于停止的问题，因此是在阶${\displaystyle \Delta _{2}^{0}}$ 的算术阶层.

并不是每个图灵等同于停机问题的集合都是停止的概率。 一个等价关系，索罗维等同，可以用来描绘制止的概率之间的左-c。e.实数 。^[4] 我们可以显示：一个在[0,1]里的实数是一个柴廷常数(即停止的概率的某些无字首的图灵完备的的可计算函数)当且仅当如果它是左-c。e. 并且是算法随机。 Ω 是少数几个 可定义的 算法随机数，它是最着名的算法随机数，但它根本不是典型的算法随机数。^[5]

不可计算性

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

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

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

算法的随机性

一个真正的数量是随机的，如果二进制序列代表实际数量是一个 算法的随机序列. 卡路德、赫特凌，寇赛诺夫 以及 王 表明，^[6] 这一递归的实数是一个算法随机的序列，当且仅当它是一个柴廷${\displaystyle \Omega }$ 数。

柴廷.mw-parser-output .serif{font-family:Times,serif}ΩU数

柴廷常数是指停机的概率，通常不是可计算数，且有无穷多个停止的概率（每个方法的程式编码都各有一个）。其中一种通用图灵机的停机概率${\displaystyle \Omega _{U}}$由卡卢德（Calude）等人计算并给出数值，约为0.007875^[7][1]：

${\displaystyle \Omega _{U}\approx \,}$0.00787499699...（OEIS数列A100264）

停机问题的不完备定理

对于每一个的一致有效的代表自然数的公理系统，如皮亚诺公理，存在常数${\displaystyle N}$使得没有“ ${\displaystyle \Omega }$ 在第${\displaystyle N}$位数 之后的位数”可以被证明为1或0，在这个系统。常数${\displaystyle N}$取决于形式系统是有效地代表，并因此并不直接反映的复杂性不言自明的系统。这个不完整的结果是类似于哥德尔不完备定理在于，它表明，没有一致的正式理论运算可以完成。

参见

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

参考文献

1. Weisstein, Eric W. (编). Chaitin's Constant. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. [2012-05-28]. （原始内容存档于2020-11-11） （英语）.
2. Downey/Hirschfeld, Theorem 6.1.3
3. Downey/Hirschfeld, Theorem 5.1.11
4. Downey/Hirschfeldt, p.405
5. Downey/Hirschfeld, p.228-229
6. Calude, Hertling, Khoussainov, and Wang. Recursively enumerable reals and Chaitin's Ω numbers (PDF). Theoretical Computer Science. 2001, 255: 125–149. （原始内容 (PDF)存档于2021-01-22）.
7. Calude, C. S.; Dinneen, M. J.; Shu, C.-K. Computing a Glimpse of Randomness (PDF). Exper. Math. 2002, 11: 361–370 [2022-09-29]. （原始内容存档 (PDF)于2022-10-18）.