柴廷常數
| 此條目翻譯品質不佳。 (2020年7月22日) |
在计算机科学中的算法信息论，柴廷常数（柴廷欧米茄数）[1]或停机的概率是一个实数，非正式地来讲，所表示的是随机的程式将会停止的概率。这些数字是从一個格雷戈里·柴廷製作的構造。
尽管有无穷多个停止的概率（每个方法的程式编码都各有一个），使用字母 Ω 代表他们是很普通的。因为 Ω 取决于程序编码使用的程式，这有时被称为柴廷構造，而不是柴廷常数当没有参考任何特定的编码的时候。
每个停止的概率是一个正规数和超越数的实数，而不是可计算数，这意味着，没有演算法计算他的位数。事实上，每个停止的概率是马丁-洛夫随机的，意味着甚至没有任何的演算法是可以可靠地猜测他的位数的。
背景
停止的概率的定义依赖于无字首的图灵完备的可计算函数的存在。这样的函数，直观地说，代表了一种编程语言具有這樣的性質：没有有效的程式可以被获得为另一个有效的程式的部分扩展。
假设 F 是一个部分函数，需要一个参数跟一个有限的二元串，并有可能返回一个二元串作为输出。这个函数F 被称为可计算的，如果有一个图灵机有计算出他(在这个意义上：对于任何有限的二元串 x 和 y、F(x)=y 若且唯若这个图灵机停止且y 在他的地带当给出输入 x的时候).
函数 F 被称为图灵完备，如果拥有下列性質：对于一个单一的变量的每个可计算函数 f ，都有一串 w 使得对於所有的 x, F(w x)= f(x)；这里 w x 表示两个二元串 w 和 x的串接. 这意味着： F 可用于模拟一个变量的任何一个可计算函数。非正式地说， w 表示可计算函数f的「腳本」，另外 F 表示一个"解释"解析脚本作为前缀的其输入和随后执行它其余的输入。
F的定义域是所有输入 p 的集合。对于图灵完备的 F，这样的p 通常可以被看到作为程式部分和数据部分的连接，并作为函数F的单一程式。
函数 F 被称为无字首如果没有两个元素 p, p′ 在其定义域使得 p′ 是p的一个部分扩展，換句話說，F 的定义域是一个前置码(瞬间代码)在有限二元串的集合。一个简单的方法來强制执行「无字首性」是使用机器，这些机器的输入是一个二流从哪位可以读一个在一段时间。 没有结束的标记；结束的输入确定通过时这个图灵完备的机器决定将停止阅读更多位数。在这里，之间的差别这两个概念的程序中提到的最后一段变得清楚的；一个是很容易地认识到一些文法，而其他需要任意的计算到承认。
定义
设 PF 是无字首的图灵完备的可计算函数 F的定义域，常数 ΩF 被定义为
- ,
表示的字串p的长度。这是一个无限和， 其中有一个加数对於F的定义域中的每個p。这要求该定义域是无字首的，再配合克拉夫特不等式，确保这个和会收敛到0到1之间的一个实数。如果 F 是明確的，则ΩF 可以被简单地写为Ω，虽然不同的无字首的图灵完备的可计算函数会有不同的Ω值。
与停机问题的关系
知道 Ω 的（二进制的）前N位数，我们可以计算出每个不超过N个字元的程式的 停机问题 。假设程式 p 其停机问题是要解决N 个字元的程式。在衔接 时，所有长度的所有程式都在运行，直到足够的程式贡献了足够的机率，以与这些「前N 位数」相配。如果程式 p 并没有停止，那么它永远也不会，因为它的贡献停止的概率将影响的第 N 位。因此，制止的问题（对於p）将得到解决。
因为有很多悬而未决的数论问题，例如哥德巴赫猜想，相当于解决特别程式(这基本上就是搜索反例，如果有一个反例发现就停止)的停机问题，知道了柴廷常数的足够位数还将意味着知道这些问题的答案。但是，由於停机问题一般並不是可以解决的，因此计算柴廷常数的任意位数是不可能的，这只是把困难的问题变成不可解決的问题，就像在试图建立一个預言机一樣。
解释作为一个机率
康托空间是所有0跟1的无限序列的集合，一个停机的概率可被解释为的测度的特定子集的康托空间在通常的概率衡量在康托空间。它是从这一解释，终止的概率取他们的名字。
该概率的测度在康托空间，有时也称为公平的硬币措施，定义，以便为任何二元字串 x 的组序列的开头 x 具有测量2−|x|. 这意味着为每个自然的数量 n，该组序列的 f 在坎特的空间，这样 f(n)=1测量的1/2和本组序列的 n个元素是0还有衡量的1/2。
设 F 是无字首的图灵完备的的可计算函数， F的定义域P包括一个二元字串的无限集合
- .
这些字符串中的每一个 pi確定了康托空间的一个子集 Si， 该组 Si包含康托空间的所有從pi开始的序列。这些都是分离的，因为 P 为无字首的集合， 总和
表示该集合的测度
- .
在这种方式， ΩF 表示的概率是随机选择的无限的0跟1的序列以F的定义域裡的一位字串(的某个有限的长度)開始，由于这个原因， ΩF 被称为停机的概率。
性質
每个柴廷常数 Ω 具有以下性質：
- 它是算法随机 (也称为马丁-洛夫随机或1-随机).[2] 这意味着！最短的程式输出的第 n 位的 Ω 必须的时间至少为 n-O(1)。 这是因为，作为在哥德巴赫的例子，这些 n 位数使我们能够找出到底哪些最多n个字元的程式将会停止。
- 它是一个正规数，这意味着，其位数出現机率都一樣，就如同他们是用「扔一个公正的硬币」來产生的。
- 它不是一个可计算数；没有可计算的函数能计算出它的值、列举它的二进制的所有位数，如下文所讨论的。
- 「有理数q使得的 q< Ω」的集合是递归可枚举集合;[3] 在递归理论，一个有这種性質的实数称为 左-c。e. 实数 .
- 「有理数q使得q> Ω」的集合不是递归可枚举的。 (原因是：每一个有这種性質的左-c。e. 实数都是可计算的，但是这个 Ω 并不是。)
- Ω 是一个 算术数.
- 这是图灵等同于停止的问题，因此是在阶 的算术阶层.
并不是每个图灵等同于停机问题的集合都是停止的概率。 一个等价关系，索罗维等同，可以用来描绘制止的概率之间的左-c。e.实数 。[4] 我们可以显示：一个在[0,1]裡的实数是一个柴廷常数(即停止的概率的某些无字首的图灵完备的的可计算函数)若且唯若如果它是左-c。e. 並且是算法随机。 Ω 是少数几个 可定义的 算法随机数，它是最着名的算法随机数，但它根本不是典型的算法随机数。[5]
不可计算性
一个实数是可计算的，如果有一个算法，给出n，返回该数的前n个位数。 这相当于存在一个程式，能夠列举数字的所有位数。
没有停机的概率是可计算的。 证明这一事实依赖于一种算法，给出Ω的前n个位数，解决图灵的停机问题对於长度不超過n的程式。由于停机问题是不可判定问題, Ω 沒有办法被计算出來。
算法进行如下。 给出 Ω 的前n个位数，以及数字k ≤ n，这个算法枚举了 F 的定义域，直到这个定义域裡足够的元素已经被找到，使他们所代表的概率是Ω的2−(k+1) . 在这一点后，没有长度k的附加程式可以在定义域裡，因为每个程式将增加2−k 到这个措施，这是不可能的。因此，长度k的字串的集合在这个定义域中就是「已经一一列举的字串的集合」。
算法的随机性
一个真正的数量是随机的，如果二进制序列代表实际数量是一个 算法的随机序列. 卡路德、赫特凌，寇賽諾夫 以及 王 表明，[6] 这一递归的实数是一个算法随机的序列，若且唯若它是一个柴廷Ω 数。
柴廷ΩU数
柴廷常數是指停機的概率，通常不是可計算數，且有無窮多個停止的概率（每個方法的程式編碼都各有一個）。其中一種通用圖靈機的停機概率 由卡盧德（Calude）等人計算並給出數值，約為0.007875[7][1]：
停机问題的不完备定理
对于每一个的一致有效的代表自然数的公理系统，如皮亚诺公理，存在常数 N 使得没有「 Ω 在第N位数 之後的位数」可以被证明为1或0，在这个系統。常数N 取决于形式系统是有效地代表，并因此并不直接反映的复杂性不言自明的系统。这个不完整的结果是类似于哥德尔不完备定理在于，它表明，没有一致的正式理论运算可以完成。
参见
参考文献
- ^ 1.0 1.1 Weisstein, Eric W. (编). . at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. [2012-05-28]. （原始内容存档于2020-11-11） （英语）.
- ^ Downey/Hirschfeld, Theorem 6.1.3
- ^ Downey/Hirschfeld, Theorem 5.1.11
- ^ Downey/Hirschfeldt, p.405
- ^ Downey/Hirschfeld, p.228-229
- ^ Calude, Hertling, Khoussainov, and Wang. (PDF). Theoretical Computer Science. 2001, 255: 125–149. （原始内容 (PDF)存档于2021-01-22）.
- ^ 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）.