柴廷常数

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

即便有无穷多个最终停机的概率（存在无穷多个针对特定图灵机的停机概率常数），我们使用字母 $\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 < \Omega})$ 是递归可枚举的。在递归论中，具有此性质的实数被称为 左递归可枚举的实数。但它不是右递归可枚举的。集合 $({ 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$常数，它才是算法随机的。

## 柴廷ΩU数

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

$\Omega_U \approx \,$0.00787499699...A100264

## 停机问题的不完备定理

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