跳转到内容

柴廷常數

维基百科,自由的百科全书

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

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

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

背景

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

假设 是一个部分函数,需要一个参数跟一个有限的二元串,并有可能返回一个二元串作为输出。这个函数被称为可计算的,如果有一个图灵机有计算出他(在这个意义上:对于任何有限的二元串 若且唯若这个图灵机停止且在他的地带当给出输入的时候).

函数被称为图灵完备,如果拥有下列性質:对于一个单一的变量的每个可计算函数 ,都有一串使得对於所有的, ;这里   表示两个二元串的串接. 这意味着:可用于模拟一个变量的任何一个可计算函数。非正式地说,表示可计算函数的「腳本」,另外表示一个"解释"解析脚本作为前缀的其输入和随后执行它其余的输入。

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

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

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

定义

是无字首的图灵完备的可计算函数的定义域,常数被定义为

,

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

与停机问题的关系

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

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

解释作为一个机率

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

该概率的测度在康托空间,有时也称为公平的硬币措施,定义,以便为任何二元字串的组序列的开头具有测量. 这意味着为每个自然的数量,该组序列的在坎特的空间,这样 测量的和本组序列的个元素是0还有衡量的

是无字首的图灵完备的的可计算函数,的定义域包括一个二元字串的无限集合

.

这些字符串中的每一个確定了康托空间的一个子集 该组包含康托空间的所有從开始的序列这些都是分离的,因为为无字首的集合, 总和

表示该集合的测度

.

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

性質

每个柴廷常数 具有以下性質:

  • 它是算法随机(也称为马丁-洛夫随机或1-随机)。[2] 这意味着!最短的程式输出的第 位的 必须的时间至少为 n-O(1)。 这是因为,作为在哥德巴赫的例子,这些 位数使我们能够找出到底哪些最多个字元的程式将会停止。
  • 它是一个正规数,这意味着,其位数出現机率都一樣,就如同他们是用「扔一个公正的硬币」來产生的。
  • 它不是一个可计算数;没有可计算的函数能计算出它的值、列举它的二进制的所有位数,如下文所讨论的。
  • 有理数使得的 」的集合是递归可枚举集合;[3]递归理论,一个有这種性質的实数称为 左-c。e. 实数 .
  • 「有理数使得」的集合不是递归可枚举的。 (原因是:每一个有这種性質的左-c。e. 实数都是可计算的,但是这个 并不是。)
  • 是一个 算术数.
  • 这是图灵等同停止的问题,因此是在阶算术阶层.

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

不可计算性

一个实数是可计算的,如果有一个算法,给出,返回该数的前个位数。 这相当于存在一个程式,能夠列举数字的所有位数。

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

算法进行如下。 给出 的前n个位数,以及数字,这个算法枚举了的定义域,直到这个定义域裡足够的元素已经被找到,使他们所代表的概率是. 在这一点后,没有长度的附加程式可以在定义域裡,因为每个程式将增加到这个措施,这是不可能的。因此,长度的字串的集合在这个定义域中就是「已经一一列举的字串的集合」。

算法的随机性

一个真正的数量是随机的,如果二进制序列代表实际数量是一个 算法的随机序列. 卡路德、赫特凌,寇賽諾夫 以及 王 表明,[6] 这一递归的实数是一个算法随机的序列,若且唯若它是一个柴廷 数。

柴廷ΩU

柴廷常數是指停機的概率,通常不是可計算數,且有無窮多個停止的概率(每個方法的程式編碼都各有一個)。其中一種通用圖靈機的停機概率由卡盧德(Calude)等人計算並給出數值,約為0.007875[7][1]

0.00787499699...(OEIS數列A100264

停机问題的不完备定理

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

参见

参考文献

  1. ^ 1.0 1.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).