柴廷常數

在計算機科學中的算法信息論，柴廷常數（柴廷歐米茄數）^[1]或停機的概率是一個實數，非正式地來講，所表示的是隨機的程式將會停止的概率。這些數字是從一個格雷戈里·柴廷製作的構造。

儘管有無窮多個停止的概率（每個方法的程式編碼都各有一個），使用字母 ${\displaystyle \Omega }$ 代表他們是很普通的。因為 ${\displaystyle \Omega }$ 取決於程序編碼使用的程式，這有時被稱為柴廷構造，而不是柴廷常數當沒有參考任何特定的編碼的時候。

每個停止的概率是一個正規數和超越數的實數，而不是可計算數，這意味着，沒有演算法計算他的位數。事實上，每個停止的概率是馬丁-洛夫隨機的，意味着甚至沒有任何的演算法是可以可靠地猜測他的位數的。

背景

停止的概率的定義依賴於無字首的圖靈完備的可計算函數的存在。這樣的函數，直觀地說，代表了一種程式語言具有這樣的性質：沒有有效的程式可以被獲得為另一個有效的程式的部分擴展。

假設 ${\displaystyle F}$是一個部分函數，需要一個參數跟一個有限的二元串，並有可能返回一個二元串作為輸出。這個函數${\displaystyle F}$被稱為可計算的，如果有一個圖靈機有計算出他(在這個意義上：對於任何有限的二元串${\displaystyle x}$和${\displaystyle y}$、${\displaystyle F(x)=y}$ 若且唯若這個圖靈機停止且${\displaystyle y}$在他的地帶當給出輸入${\displaystyle x}$的時候).

函數${\displaystyle F}$被稱為圖靈完備，如果擁有下列性質：對於一個單一的變量的每個可計算函數${\displaystyle f}$ ，都有一串${\displaystyle w}$使得對於所有的${\displaystyle x}$, ${\displaystyle F(w\,x)=f(x)}$；這裏 ${\displaystyle w}$ ${\displaystyle x}$ 表示兩個二元串${\displaystyle w}$和${\displaystyle x}$的串接. 這意味着：${\displaystyle F}$可用於模擬一個變量的任何一個可計算函數。非正式地說，${\displaystyle w}$表示可計算函數${\displaystyle f}$的「腳本」，另外${\displaystyle F}$表示一個"解釋"解析腳本作為前綴的其輸入和隨後執行它其餘的輸入。

${\displaystyle F}$的定義域是所有輸入${\displaystyle p}$的集合。對於圖靈完備的${\displaystyle F}$，這樣的${\displaystyle p}$通常可以被看到作為程式部分和數據部分的連接，並作為函數${\displaystyle F}$的單一程式。

函數${\displaystyle F}$被稱為無字首如果沒有兩個元素 ${\displaystyle p}$, ${\displaystyle p'}$在其定義域使得${\displaystyle p'}$是${\displaystyle p}$的一個部分擴展，換句話說，${\displaystyle F}$的定義域是一個前置碼（瞬間代碼）在有限二元串的集合。一個簡單的方法來強制執行「無字首性」是使用機器，這些機器的輸入是一個二流從哪位可以讀一個在一段時間。 沒有結束的標記；結束的輸入確定通過時這個圖靈完備的機器決定將停止閱讀更多位數。在這裏，之間的差別這兩個概念的程序中提到的最後一段變得清楚的；一個是很容易地認識到一些文法，而其他需要任意的計算到承認。

任何圖靈完備的可計算函數的定義域都是遞歸可枚舉集合，但是不是遞歸集合. 這個定義域是圖靈等同於停機問題.

定義

設${\displaystyle P_{F}}$是無字首的圖靈完備的可計算函數${\displaystyle F}$的定義域，常數${\displaystyle \Omega _{F}}$被定義為

${\displaystyle \Omega _{F}=\sum _{p\in P_{F}}2^{-|p|}}$,

${\displaystyle \left|p\right|}$ 表示的字串${\displaystyle p}$的長度。這是一個無限和， 其中有一個加數對於${\displaystyle F}$的定義域中的每個${\displaystyle p}$。這要求該定義域是無字首的，再配合克拉夫特不等式，確保這個和會收斂到0到1之間的一個實數。如果${\displaystyle F}$是明確的，則${\displaystyle \Omega _{F}}$可以被簡單地寫為${\displaystyle \Omega }$，雖然不同的無字首的圖靈完備的可計算函數會有不同的${\displaystyle \Omega }$值。

與停機問題的關係

知道${\displaystyle \Omega }$的（二進制的）前${\displaystyle N}$位數，我們可以計算出每個不超過${\displaystyle N}$個字元的程式的 停機問題 。假設程式${\displaystyle p}$其停機問題是要解決${\displaystyle N}$個字元的程式。在銜接時，所有長度的所有程式都在運行，直到足夠的程式貢獻了足夠的機率，以與這些「前${\displaystyle N}$位數」相配。如果程式${\displaystyle p}$並沒有停止，那麼它永遠也不會，因為它的貢獻停止的概率將影響的第${\displaystyle N}$位。因此，制止的問題（對於${\displaystyle p}$）將得到解決。

因為有很多懸而未決的數論問題，例如哥德巴赫猜想，相當於解決特別程式（這基本上就是搜索反例，如果有一個反例發現就停止）的停機問題，知道了柴廷常數的足夠位數還將意味着知道這些問題的答案。但是，由於停機問題一般並不是可以解決的，因此計算柴廷常數的任意位數是不可能的，這只是把困難的問題變成不可解決的問題，就像在試圖建立一個預言機一樣。

解釋作為一個機率

康托空間是所有0跟1的無限序列的集合，一個停機的概率可被解釋為的測度的特定子集的康托空間在通常的概率衡量在康托空間。它是從這一解釋，終止的概率取他們的名字。

該概率的測度在康托空間，有時也稱為公平的硬幣措施，定義，以便為任何二元字串${\displaystyle x}$的組序列的開頭${\displaystyle x}$具有測量${\displaystyle 2^{-\left\vert x\right\vert }}$. 這意味着為每個自然的數量${\displaystyle n}$，該組序列的${\displaystyle f}$在坎特的空間，這樣 ${\displaystyle f(n)=1}$測量的${\displaystyle {\frac {1}{2}}}$和本組序列的${\displaystyle n}$個元素是0還有衡量的${\displaystyle {\frac {1}{2}}}$。

設${\displaystyle F}$是無字首的圖靈完備的的可計算函數，${\displaystyle F}$的定義域${\displaystyle P}$包括一個二元字串的無限集合

${\displaystyle P=\{p_{1},p_{2},\ldots \}}$.

這些字符串中的每一個${\displaystyle pi}$確定了康托空間的一個子集${\displaystyle Si}$， 該組${\displaystyle Si}$包含康托空間的所有從${\displaystyle pi}$開始的序列。這些都是分離的，因為${\displaystyle P}$為無字首的集合， 總和

${\displaystyle \sum _{p\in P}2^{-|p|}}$

表示該集合的測度

${\displaystyle \bigcup _{i\in \mathbb {N} }S_{i}}$.

在這種方式， ${\displaystyle \Omega _{F}}$表示的概率是隨機選擇的無限的0跟1的序列以F的定義域裏的一位字串（的某個有限的長度）開始，由於這個原因，${\displaystyle \Omega _{F}}$被稱為停機的概率。

性質

每個柴廷常數 ${\displaystyle \Omega }$ 具有以下性質：

• 它是算法隨機（也稱為馬丁-洛夫隨機或1-隨機）。^[2] 這意味着！最短的程式輸出的第 ${\displaystyle n}$ 位的 ${\displaystyle \Omega }$ 必須的時間至少為 n-O(1)。 這是因為，作為在哥德巴赫的例子，這些 ${\displaystyle n}$ 位數使我們能夠找出到底哪些最多${\displaystyle n}$個字元的程式將會停止。
• 它是一個正規數，這意味着，其位數出現機率都一樣，就如同他們是用「扔一個公正的硬幣」來產生的。
• 它不是一個可計算數；沒有可計算的函數能計算出它的值、列舉它的二進制的所有位數，如下文所討論的。
• 「有理數${\displaystyle q}$使得的 ${\displaystyle q<\Omega }$」的集合是遞歸可枚舉集合;^[3] 在遞歸理論，一個有這種性質的實數稱為 左-c。e. 實數 .
• 「有理數${\displaystyle q}$使得${\displaystyle q>\Omega }$」的集合不是遞歸可枚舉的。 (原因是：每一個有這種性質的左-c。e. 實數都是可計算的，但是這個 ${\displaystyle \Omega }$ 並不是。)
• ${\displaystyle \Omega }$ 是一個 算術數.
• 這是圖靈等同於停止的問題，因此是在階${\displaystyle \Delta _{2}^{0}}$ 的算術階層.

並不是每個圖靈等同於停機問題的集合都是停止的概率。 一個等價關係，索羅維等同，可以用來描繪製止的概率之間的左-c。e.實數 。^[4] 我們可以顯示：一個在[0,1]裏的實數是一個柴廷常數(即停止的概率的某些無字首的圖靈完備的的可計算函數)若且唯若如果它是左-c。e. 並且是算法隨機。 Ω 是少數幾個 可定義的 算法隨機數，它是最着名的算法隨機數，但它根本不是典型的算法隨機數。^[5]

不可計算性

一個實數是可計算的，如果有一個算法，給出${\displaystyle n}$，返回該數的前${\displaystyle n}$個位數。 這相當於存在一個程式，能夠列舉數字的所有位數。

沒有停機的概率是可計算的。 證明這一事實依賴於一種算法，給出${\displaystyle \Omega }$的前${\displaystyle n}$個位數，解決圖靈的停機問題對於長度不超過${\displaystyle n}$的程式。由於停機問題是不可判定問題，${\displaystyle \Omega }$沒有辦法被計算出來。

算法進行如下。 給出 ${\displaystyle \Omega }$ 的前n個位數，以及數字${\displaystyle k\leq n}$，這個算法枚舉了${\displaystyle F}$的定義域，直到這個定義域裏足夠的元素已經被找到，使他們所代表的概率是${\displaystyle \Omega }$的${\displaystyle 2^{-(k+1)}}$. 在這一點後，沒有長度${\displaystyle k}$的附加程式可以在定義域裏，因為每個程式將增加${\displaystyle 2^{-k}}$到這個措施，這是不可能的。因此，長度${\displaystyle k}$的字串的集合在這個定義域中就是「已經一一列舉的字串的集合」。

算法的隨機性

一個真正的數量是隨機的，如果二進制序列代表實際數量是一個 算法的隨機序列. 卡路德、赫特凌，寇賽諾夫 以及 王 表明，^[6] 這一遞歸的實數是一個算法隨機的序列，若且唯若它是一個柴廷${\displaystyle \Omega }$ 數。

柴廷.mw-parser-output .serif{font-family:Times,serif}ΩU數

柴廷常數是指停機的概率，通常不是可計算數，且有無窮多個停止的概率（每個方法的程式編碼都各有一個）。其中一種通用圖靈機的停機概率${\displaystyle \Omega _{U}}$由卡盧德（Calude）等人計算並給出數值，約為0.007875^[7][1]：

${\displaystyle \Omega _{U}\approx \,}$0.00787499699...（OEIS數列A100264）

停機問題的不完備定理

對於每一個的一致有效的代表自然數的公理系統，如皮亞諾公理，存在常數${\displaystyle N}$使得沒有「 ${\displaystyle \Omega }$ 在第${\displaystyle N}$位數 之後的位數」可以被證明為1或0，在這個系統。常數${\displaystyle N}$取決於形式系統是有效地代表，並因此並不直接反映的複雜性不言自明的系統。這個不完整的結果是類似於哥德爾不完備定理在於，它表明，沒有一致的正式理論運算可以完成。

參見

• 不完備定理
• 柯氏複雜性

參考文獻

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）.