蔡廷常數

蔡廷常數，也稱為蔡廷 Omega 數，由蔡廷 (1975) 引入，是通用字首碼（自限定）圖靈機的停機機率。每個蔡廷常數同時是可計算可列舉的（有理數的可計算、遞增、收斂序列的極限），並且是演算法隨機的（其二進位制展開是演算法隨機序列），因此是不可計算的 (Chaitin 1975)。

因此，蔡廷常數可以定義為

(1)

這給出了對於任何指令集，特定的字首碼通用圖靈機將停機的機率，其中 是程式 的位元大小。

蔡廷常數的值高度依賴於機器。在某些情況下，甚至可以證明無法計算單個位元 (Solovay 2000)。

蔡廷常數 可能是不可計算數字最明顯的具體例子。它們也被認為是超越數。

Calude 等人 (2002) 計算了某個通用圖靈機的蔡廷常數 的前 64 位，結果為

			(2)
			(3)

(OEIS A079365 和 A100264)。

Calude 和 Dinneen (2007) 隨後計算了另一個字首碼圖靈機的前 43 位和 40 位，該圖靈機在使用基數為 16 和 2 的資料時分別是通用的，結果為

			(4)
			(5)

二進位制結果被刻在 Stephen Wolfram 為 Gregory Chaitin 60 歲生日贈送的獎章上，如上圖所示。