查看“︁柴廷常數”︁的源代码

{{Rough translation|time=2020-07-22T10:51:40+00:00}}
在[[计算机科学]]中的[[算法信息论]]，'''柴廷常数'''（'''柴廷欧米茄数'''）<ref name="mathworld">{{cite mathworld|urlname=ChaitinsConstant|title=Chaitin's Constant|archive-url=https://web.archive.org/web/20201111211149/http://mathworld.wolfram.com/ChaitinsConstant.html|archive-date=2020-11-11|accessdate=2012-05-28}}</ref>或'''停机的概率'''是一个[[实数]]，非正式地来讲，所表示的是随机的程式将会停止的[[概率]]。这些数字是从一個格雷戈里·柴廷製作的構造。

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

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

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

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

函数<math>F</math>被称为'''[[圖靈完備性|图灵完备]]'''，如果拥有下列性質：对于一个单一的变量的每个可计算函数<math>f</math> ，都有一串<math>w</math>使得对於所有的<math>x</math>, <math>F(w\, x)= f(x)</math>；这里 ''<math>w</math>''&nbsp;''<math>x</math>'' 表示两个二元串''<math>w</math>''和''<math>x</math>''[[串接|的串接]]. 这意味着：<math>F</math>可用于模拟一个变量的任何一个可计算函数。非正式地说，''<math>w</math>''表示可计算函数''<math>f</math>的「腳本」，另外''<math>F</math>表示一个"解释"解析脚本作为前缀的其输入和随后执行它其余的输入。

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

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

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

== 定义 ==
设<math>P_F</math>是无字首的图灵完备的可计算函数<math>F</math>的定义域，常数<math>\Omega_F</math>被定义为

: <math>\Omega_F = \sum_{p \in P_F} 2^{-|p|}</math>,

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

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

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

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

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

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

: <math>P = \{p_1,p_2,\ldots\}</math>.

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

: <math>\sum_{p \in P} 2^{-|p|}</math>

表示该集合的测度

: <math>\bigcup_{i \in \mathbb{N}} S_i</math>.

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

== 性質 ==
每个柴廷常数 <math>\Omega</math> 具有以下性質：

* 它是算法随机（也称为马丁-洛夫随机或1-随机）。<ref>Downey/Hirschfeld, Theorem 6.1.3</ref> 这意味着！最短的程式输出的第 <math>n</math> 位的 <math>\Omega</math> 必须的时间至少为 ''n''-O(1)。 这是因为，作为在哥德巴赫的例子，这些 ''<math>n</math>'' 位数使我们能够找出到底哪些最多<math>n</math>个字元的程式将会停止。
* 它是一个[[正规数]]，这意味着，其位数出現机率都一樣，就如同他们是用「扔一个公正的硬币」來产生的。
* 它不是一个[[可計算數|可计算数]]；没有可计算的函数能计算出它的值、列举它的二进制的所有位数，如下文所讨论的。
* 「[[有理数]]<math>q</math>使得的 <math>q<\Omega</math>」的集合是[[递归可枚举集合]];<ref>Downey/Hirschfeld, Theorem 5.1.11</ref> 在[[可计算性理论|递归理论]]，一个有这種性質的实数称为 '''左-c。e. 实数''' .
* 「有理数<math>q</math>使得<math>q>\Omega</math>」的集合不是递归可枚举的。 (原因是：每一个有这種性質的左-c。e. 实数都是可计算的，但是这个 <math>\Omega</math> 并不是。)
* <math>\Omega</math> 是一个 算术数.
* 这是[[不可解度|图灵等同]]于[[停机问题|停止的问题]]，因此是在阶<math>\Delta^0_2</math> 的[[算数阶层|算术阶层]].

并不是每个图灵等同于停机问题的集合都是停止的概率。 一个[[等价关系]]，索罗维'''等同'''，可以用来描绘制止的概率之间的左-c。e.实数 。<ref name=":0">Downey/Hirschfeldt, p.405</ref> 我们可以显示：一个在[0,1]裡的实数是一个柴廷常数(即停止的概率的某些无字首的图灵完备的的可计算函数)若且唯若如果它是左-c。e. 並且是算法随机。 &#x3A9; 是少数几个 [[可定义数|可定义的]] 算法随机数，它是最着名的算法随机数，但它根本不是典型的算法随机数。<ref>Downey/Hirschfeld, p.228-229</ref>

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

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

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

== 算法的随机性 ==
一个真正的数量是随机的，如果二进制序列代表实际数量是一个 算法的随机序列. 
卡路德、赫特凌，寇賽諾夫 以及 王 表明，<ref>{{Cite journal|author=Calude, Hertling, Khoussainov, and Wang| title= Recursively enumerable reals and Chaitin's {{math|&#x3A9;}} numbers | url=http://webpages.uncc.edu/yonwang/papers/TCS01.pdf |journal = Theoretical Computer Science | volume = 255 | pages= 125–149|year= 2001 | archive-url=https://web.archive.org/web/20210122150412/http://webpages.uncc.edu/yonwang/papers/TCS01.pdf|archive-date=2021-01-22}}</ref>
这一递归的实数是一个算法随机的序列，若且唯若它是一个柴廷<math>\Omega</math> 数。

== 柴廷{{math|&#x3A9;<sub>''U''</sub>}}数 ==
柴廷常數是指停機的概率，通常不是[[可計算數]]，且有無窮多個停止的概率（每個方法的程式編碼都各有一個）。其中一種通用圖靈機的停機概率<math>\Omega_U</math>由卡盧德（Calude）等人計算並給出數值，約為0.007875<ref>{{Cite journal|author=Calude, C. S.; Dinneen, M. J.; Shu, C.-K.|title=Computing a Glimpse of Randomness|url=https://www.cs.auckland.ac.nz/~cristian/Calude361_370.pdf|journal=Exper. Math|volume=11|pages=361-370|year=2002|access-date=2022-09-29|archive-date=2022-10-18|archive-url=https://web.archive.org/web/20221018021306/https://cs.auckland.ac.nz/~cristian/Calude361_370.pdf|dead-url=no}}</ref><ref name="mathworld"/>：
:<math>\Omega_U \approx \,</math>0.00787499699...{{OEIS|A100264}}

== 停机问題的不完备定理 ==
对于每一个的一致有效的代表自然数的[[公理系统]]，如[[皮亚诺公理]]，存在常数<math>N</math>使得没有「 <math>\Omega</math> 在''第<math>N</math>位数 之後的位数」''可以被证明为1或0，在这个系統。常数<math>N</math>取决于[[形式系統|形式系统]]是有效地代表，并因此并不直接反映的复杂性不言自明的系统。这个不完整的结果是类似于[[哥德尔不完备定理]]在于，它表明，没有一致的正式理论运算可以完成。

== 参见 ==

* [[哥德尔不完备定理|不完备定理]]
* [[柯氏复杂性]]

==参考文献==
{{reflist}}
{{無理數導航}}
[[Category:算法信息论]]
[[Category:計算理論]]
[[Category:实数超越数]]