柴廷常數

在電腦科學的演算法資訊理論中，柴廷常數（也稱柴廷歐米茄數）或任意隨機圖靈機停機的機率是一個實數。即，柴廷常數代表著隨機生成的程序在通用圖靈機上最終將會停機的機率。這一數字被格雷戈里·柴廷所構造。

即便有無窮多個最終停機的機率（存在無窮多個針對特定圖靈機的停機機率常數），我們使用字母 $\Omega$ 表示特定的前綴無符號通用圖靈機最終停機的機率的統稱。由於 $\Omega$ 取決於圖靈機具體編碼的細節，因此在不指代任何特定圖靈機的編碼方式時，它常被稱為柴廷構造而非柴廷常數。

每個圖靈機所停機的機率是一個正規且超越的實數，且這一機率並不是可計算數。因為每個特定圖靈機所停機的機率是馬丁-洛夫隨機的，沒有演算法可以用於計算它的實際位數。

## 背景

停機機率的定義基於前綴無符號通用可計算函數的存在。直觀地說，這種函數代表了一種特殊的程式語言，即其中沒有任何合法的程序代碼是另一個合法程序的前綴（即不存在一個有效程序可以通過在另一個有效程序末尾添加字符得到）。

設 $F$為一個接受有限二進位字串作為參數、且可能輸出單個二進位字串的偏函數。若存在任意一個圖靈機可以計算該函數，則這個函數$F$被稱為可計算的。具體來說，對於任何有限的二進位字串$x$和$y$，若且唯若該圖靈機在以$x$作為輸入時最終停機，且最終磁帶上的內容為$y$。

如果對於每一個單變量的可計算函數 $f$ 都存在一個字串 $w$ 使得對於所有 $x$ 都有 $F(w,x)=f(x)$，那麼函數 $F$ 就被稱為計算通用的，其中 $w,x$ 表示兩個字串 $w$ 和 $x$ 的串接。這意味著 $F$ 可用於模擬任何單變量可計算函數。換句話說，$w$ 代表可計算函數 $f$ 的一段「腳本」，而 $F$ 則代表一個「解釋器」，它將腳本解析為其輸入的前綴，然後在輸入的剩餘部分上執行它。

$F$ 的定義域是使其有定義的所有輸入 $p$ 的集合。對於通用的 $F$，這樣的 $p$ 通常既可以看作程序部分和數據部分的連接，也可以看作函數 $F$ 的單個程序。

如果函數 $F$ 的定義域中不存在兩個元素 $p$、$p'$，使得 $p'$ 是 $p$ 的真擴展，則稱 $F$ 是無前綴的。這可以重新表述為：$F$ 的定義域是有限二進位字串集合上的一個前置碼（即時碼）。一種強制無前綴性的簡單方法是使用以二進位流作為輸入方式的機器，比特位可以被逐位讀取。這裡沒有流結束標記；輸入的結束由通用機器決定何時停止讀取更多比特來確定，而剩餘的比特不被視為已接受字串的一部分。在此，上段提到的兩種程序概念之間的區別就變得清晰了：一種很容易被某種形式語法識別，而另一種則需要任意計算才能識別。

任何通用可計算函數的定義域都是一個遞歸可枚舉集合，但並不是遞歸可計算的。它的定義域在不可解度上等價於停機問題。

## 定義

設$P_F$是無字首的圖靈完備的可計算函數$F$的定義域，常數$\Omega_F$被定義為

$\Omega_F = \sum_{p \in P_F} 2^{-|p|}$,

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

## 與停機問題的關係

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

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

## 解釋作為一個機率

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

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

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

$P = \{p_1,p_2,\ldots\}$.

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

$$\sum_{p \in P} 2^{-|p|}$$

表示該集合的測度

$\bigcup_{i \in \mathbb{N}} S_i$.

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

## 性質

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

- 是演算法隨機的（也稱為馬丁-洛夫隨機或 1-隨機）。這意味著，要確定 $\Omega$ 的前 $n$ 位二進位展開，任何程序都必須使用至少 $(n - O(1))$ 位的資訊。直觀地說，$\Omega$ 的前 $n$ 位包含了關於所有長度不超過 $n$ 的程序是否停機的不可壓縮資訊。例如，利用這些位可以判定哪些長度至多為 $n$ 的無前綴程序會停機。
- 它是一個正規數。即在其二進位展開中，每一位（0或1）出現的頻率趨於相等，整體表現為「如同反覆拋擲一枚公平的硬幣」生成。
- 它不是一個可計算數。不存在圖靈機能夠逐位列出其完整的二進位展開，如下文所討論的。
- 它具有左遞歸可枚舉性。集合 $({q \in \mathbb{Q} \mid q < \Omega})$ 是遞歸可枚舉的。在遞歸論中，具有此性質的實數被稱為 左遞歸可枚舉的實數。但它不是右遞歸可枚舉的。集合 $({ q \in \mathbb{Q} \mid q > \Omega })$ 不是遞歸可枚舉的。若一個實數既是左遞歸可枚舉又是右遞歸可枚舉的（即其上下逼近均可枚舉），則它必為可計算數；但 $\Omega$ 不可計算，故其上界集不可枚舉。
- 它是一個算術數。
- 它在不可解度上等價于于停機問題，因此屬於算術階層的第$\Delta^0_2$階。

但並非所有圖靈等價於停機問題的實數都是柴廷常數。通過一種稱為 索洛維等同的等價關係，可以在左遞歸可枚舉的實數中描述哪些是真正的停機機率。若且唯若一個實數既是左遞歸可枚舉的，又是演算法隨機的，這一實數 $(\alpha \in [0,1])$才屬於某個無前綴通用圖靈機的柴廷常數。

儘管 $\Omega$ 是少數幾個明確可定義的演算法隨機數中最著名的例子之一，但它在演算法隨機數的全體中並不「典型」，因為大多數演算法隨機數甚至是不可定義的。

## 不可計算性

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

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

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

## 演算法隨機性

若表示某個實數的二進位序列屬於演算法隨機序列，則稱這個實數是「隨機的」。Calude、Hertling、Khoussainov與Wang證明了，若且唯若一個遞歸可枚舉實數是某個特定圖靈機的蔡廷$\Omega$常數，它才是演算法隨機的。

## 柴廷ΩU數

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

$\Omega_U \approx \,$0.00787499699...A100264

## 停機問題的不完備定理

對於每個一致且可以表示自然數的公理系統（如皮亞諾公理）而言，都存在一個常數$N$使得該系統中$\Omega$的二進位表示中第$N$位後的任何位都不能被證明為1或0。這個常數$N$取決於該形式系統的有效表示方式，因而並不能反映公理系統本身的複雜性。這一不完備性的結果與哥德爾不完備定理類似，均表明任何一致的算術形式理論都不是完備的。