柴廷常數

在計算機科學中的演算法資訊理論，柴廷常數或停機的機率是一個實數，非正式地來講，所表示的是隨機的程式將會停止的機率。這些數字是從一個格雷戈裡·柴廷製作的構造。儘管有無窮多個停止的機率，使用字母 formula_1 代表他們是很普通的。因為 formula_1 取決於程式編碼使用的程式，這有時被稱為柴廷構造，而不是柴廷常數當沒有參考任何特定的編碼的時候。每個停止的機率是一個正規數和超越數的實數，而不是可計算數，這意味著，沒有演演算法計算他的位數。事實上，每個停止的機率是馬丁-洛夫隨機的，意味著甚至沒有任何的演演算法是可以可靠地猜測他的位數的。背景.停止的機率的定義依賴於無字首的圖靈完備的可計算函式的存在。這樣的函式，直觀地說，代表了一種程式語言具有這樣的性質：沒有有效的程式可以被獲得為另一個有效的程式的部分擴充套件。假設 formula_3是一個部分函式，需要一個引數跟一個有限的二元串，並有可能返回一個二元串作為輸出。這個函式formula_3被稱為可計算的，如果有一個圖靈機有計算出他(在這個意義上：對於任何有限的二元串formula_5和formula_6"、"formula_7 若且唯若這個圖靈機停止且formula_6在他的地帶當給出輸入formula_5"的時候)."函式formula_3被稱為圖靈完備，如果擁有下列性質：對於一個單一的變數的每個可計算函式formula_11 ，都有一串formula_12使得對於所有的formula_5, formula_14；這裡 "formula_12" "formula_5" 表示兩個二元串"formula_12"和"formula_5"的串接. 這意味著：formula_3可用於模擬一個變數的任何一個可計算函式。非正式地說，"formula_12"表示可計算函式"formula_11的「指令碼」，另外"formula_3表示一個"解釋"解析指令碼作為字首的其輸入和隨後執行它其餘的輸入。formula_3的定義域是所有輸入formula_24的集合。對於圖靈完備的formula_3，這樣的formula_24通常可以被看到作為程式部分和資料部分的連線，並作為函式formula_3的單一程式。函式formula_3被稱為無字首如果沒有兩個元素 formula_24, formula_30在其定義域使得formula_30是formula_24的一個部分擴充套件，換句話說，formula_3的定義域是一個前置碼在有限二元串的集合。一個簡單的方法來強制執行「無字首性」是使用機器，這些機器的輸入是一個二流從哪位可以讀一個在一段時間。 沒有結束的標記；結束的輸入確定透過時這個圖靈完備的機器決定將停止閱讀更多位數。在這裡，之間的差別這兩個概念的程式中提到的最後一段變得清楚的；一個是很容易地認識到一些文法，而其他需要任意的計算到承認。任何圖靈完備的可計算函式的定義域都是遞迴可列舉集合，但是不是遞迴集合. 這個定義域是圖靈等同於停機問題.定義.設formula_34是無字首的圖靈完備的可計算函式formula_3的定義域，常數formula_36被定義為formula_37,formula_38 表示的字串formula_24的長度。這是一個無限和， 其中有一個加數對於formula_3的定義域中的每個formula_24。這要求該定義域是無字首的，再配合克拉夫特不等式，確保這個和會收斂到0到1之間的一個實數。如果formula_3是明確的，則formula_36可以被簡單地寫為formula_1，雖然不同的無字首的圖靈完備的可計算函式會有不同的formula_1值。與停機問題的關係.知道formula_1的將得到解決。因為有很多懸而未決的數論問題，例如哥德巴赫猜想，相當於解決特別程式的停機問題，知道了柴廷常數的足夠位數還將意味著知道這些問題的答案。但是，由於停機問題一般並不是可以解決的，因此計算柴廷常數的任意位數是不可能的，這只是把困難的問題變成不可解決的問題，就像在試圖建立一個預言機一樣。解釋作為一個機率.康託空間是所有0跟1的無限序列的集合，一個停機的機率可被解釋為的測度的特定子集的康託空間在通常的機率衡量在康託空間。它是從這一解釋，終止的機率取他們的名字。該機率的測度在康託空間，有時也稱為公平的硬幣措施，定義，以便為任何二元字串formula_5的組序列的開頭formula_5具有測量formula_57. 這意味著為每個自然的數量formula_58，該組序列的formula_11在坎特的空間，這樣 formula_60測量的formula_61和本組序列的formula_58個元素是0還有衡量的formula_61。設formula_3是無字首的圖靈完備的的可計算函式，formula_3的定義域formula_66包括一個二元字串的無限集合formula_67.這些字串中的每一個formula_68"確定了康託空間的"一個子集formula_69"，" 該組formula_69包含康託空間的所有從formula_68開始的序列"。"這些都是分離的，因為formula_66為無字首的集合， 總和formula_73表示該集合的測度formula_74.在這種方式， formula_36表示的機率是隨機選擇的無限的0跟1的序列以F的定義域裡的一位字串開始，由於這個原因，formula_36被稱為停機的機率。性質.每個柴廷常數 formula_1 具有以下性質：並不是每個圖靈等同於停機問題的集合都是停止的機率。 一個等價關係，索羅維等同，可以用來描繪製止的機率之間的左-c。e.實數 。 我們可以顯示：一個在[0,1]裡的實數是一個柴廷常數(即停止的機率的某些無字首的圖靈完備的的可計算函式)若且唯若如果它是左-c。e. 並且是演算法隨機。 Ω 是少數幾個 可定義的 演算法隨機數，它是最著名的演算法隨機數，但它根本不是典型的演算法隨機數。不可計算性.一個實數是可計算的，如果有一個演算法，給出"formula_58"，返回該數的前formula_58個位數。 這相當於存在一個程式，能夠列舉數字的所有位數。沒有停機的機率是可計算的。 證明這一事實依賴於一種演算法，給出formula_1的前formula_58個位數，解決圖靈的停機問題對於長度不超過formula_58的程式。由於停機問題是不可判定問題，formula_1沒有辦法被計算出來。演算法進行如下。 給出 formula_1 的前n個位數，以及數字formula_96，這個演算法枚舉了formula_3的定義域，直到這個定義域裡足夠的元素已經被找到，使他們所代表的機率是formula_1的formula_99. 在這一點後，沒有長度formula_100的附加程式可以在定義域裡，因為每個程式將增加formula_101到這個措施，這是不可能的。因此，長度formula_100的字串的集合在這個定義域中就是「已經一一列舉的字串的集合」。演算法的隨機性.一個真正的數量是隨機的，如果二進位制序列代表實際數量是一個 演算法的隨機序列.卡路德、赫特凌，寇賽諾夫 以及 王 表明，這一遞迴的實數是一個演算法隨機的序列，若且唯若它是一個柴廷formula_1 數。柴廷Ω"U"數.柴廷常數是指停機的機率，通常不是可計算數，且有無窮多個停止的機率等人計算並給出數值，約為0.007875：formula_1050.00787499699...停機問題的不完備定理.對於每一個的一致有效的代表自然數的公理系統，如皮亞諾公理，存在常數formula_47使得沒有「 formula_1 在"第formula_47位數 之後的位數」"可以被證明為1或0，在這個系統。常數formula_47取決於形式系統是有效地代表，並因此並不直接反映的複雜性不言自明的系統。這個不完整的結果是類似於哥德爾不完備定理在於，它表明，沒有一致的正式理論運算可以完成。