蔡廷常数

蔡廷常数，也称为蔡廷 Omega 数，由蔡廷 (1975) 引入，是通用前缀码（自限定）图灵机的停机概率。每个蔡廷常数同时是可计算可枚举的（有理数的可计算、递增、收敛序列的极限），并且是算法随机的（其二进制展开是算法随机序列），因此是不可计算的 (Chaitin 1975)。

因此，蔡廷常数可以定义为

(1)

这给出了对于任何指令集，特定的前缀码通用图灵机将停机的概率，其中 是程序 的比特大小。

蔡廷常数的值高度依赖于机器。在某些情况下，甚至可以证明无法计算单个比特 (Solovay 2000)。

蔡廷常数 可能是不可计算数字最明显的具体例子。它们也被认为是超越数。

Calude 等人 (2002) 计算了某个通用图灵机的蔡廷常数 的前 64 位，结果为

			(2)
			(3)

(OEIS A079365 和 A100264)。

Calude 和 Dinneen (2007) 随后计算了另一个前缀码图灵机的前 43 位和 40 位，该图灵机在使用基数为 16 和 2 的数据时分别是通用的，结果为

			(4)
			(5)

二进制结果被刻在 Stephen Wolfram 为 Gregory Chaitin 60 岁生日赠送的奖章上，如上图所示。