[科普中國]-丘奇論題

假說前提

已知的三種計(jì)算過程（遞歸，λ演算和圖靈機(jī)）都是等價的--這三種方法定義了同一類函數(shù)。這導(dǎo)致數(shù)學(xué)家和計(jì)算機(jī)科學(xué)家相信可計(jì)算性的概念可由上述三種等價的計(jì)算過程描述。簡單來講，邱奇-圖靈論題認(rèn)為如果某種方法（算法）可進(jìn)行運(yùn)算，那么該運(yùn)算也可被圖靈機(jī)執(zhí)行（也可被遞歸定義的函數(shù)或λ函數(shù)執(zhí)行）。

邱奇-圖靈論題是對計(jì)算特性進(jìn)行描述的一種陳述，故而不能被嚴(yán)格證明。雖然上面提到的三種計(jì)算過程可被證明為等價的，但是邱奇-圖靈論題最根本的前提--聲稱一個函數(shù)是“可有效計(jì)算的”究竟意味著什么--在某種意義上是不甚明確的直覺結(jié)果。所以，該論題依然是一個假想。2

盡管邱奇-圖靈論題不能被證明，到目前為止它仍然受到近乎全面的接受。

正式闡述Rosser于1939年對“可有效計(jì)算性”進(jìn)行了如下的解讀：“很明顯CC和RC（邱奇和Rosser的論據(jù)）的成立依賴于對‘有效性’的嚴(yán)格定義?！行У姆椒ā饕侵冈摲椒ǖ拿恳徊蕉伎杀皇孪却_定，而且該方法可在有限的步數(shù)之內(nèi)生成結(jié)果”。因此，‘有效性’實(shí)際上包含兩層含義：3

（1）產(chǎn)生一種確定的，或者所需的效果；

（2）能夠產(chǎn)生計(jì)算結(jié)果。

接下來， 術(shù)語“可有效演算的”意味著“由任何直觀上有效的方法產(chǎn)生的”，而術(shù)語“可有效計(jì)算的”意味著“由圖靈機(jī)或任何等價的機(jī)械設(shè)備產(chǎn)生的”。圖靈本人對此的定義由他在1939年的博士論文“基于有序數(shù)的邏輯系統(tǒng)”的腳注中給出：“我們應(yīng)該使用‘可計(jì)算函數(shù)’來表示一個可被機(jī)器計(jì)算的函數(shù)， 使用‘可有效演算的’來指代那些并未特別指明的直觀想法?！?/p>

這可以轉(zhuǎn)述為：任何可有效演算的函數(shù)都是可計(jì)算函數(shù)。

圖靈則是如此描述的：“當(dāng)一個函數(shù)的值可由某種純機(jī)械計(jì)算步驟得到時， 它就是可有效演算的函數(shù)...應(yīng)該這樣認(rèn)識： 可計(jì)算性和可有效演算性是不同的?！?/p>

等價形式本論題的另外一種說法就是邏輯和數(shù)學(xué)中的有效或機(jī)械方法可由圖靈機(jī)來表示。通常我們假定這些方法必須滿足以下的要求：4

一個方法由有限多簡單和精確的指令組成，這些指令可由有限多的符號來描述。

該方法總會在有限的步驟內(nèi)產(chǎn)生出一個結(jié)果。

基本上人可以僅用紙張和鉛筆來執(zhí)行。

該方法的執(zhí)行不需人類的智慧來理解和執(zhí)行這些指令。

此類方法的一個范例便是用于確定兩個自然數(shù)的最大公約數(shù)的歐基里德算法。

“有效方法”這個想法在直覺上是清楚的，但卻沒有在形式上加以定義，因?yàn)槭裁词恰耙粋€簡單而精確的指令”和什么是“執(zhí)行這些指令所需的智力”這兩個問題并沒有明確的答案。（如需歐幾里得算法之外的范例，請參見數(shù)論中的有效結(jié)果。）

起源在他1936年的論文“論可計(jì)算數(shù)字，及其在判定性問題（德語：Entscheidungsproblem）中的應(yīng)用”中，阿蘭·圖靈試圖通過引入圖靈機(jī)來形式地展示這一想法。在此篇論文中，他證明了“判定性問題”是無法解決的。幾個月之前，阿隆佐·邱奇在“關(guān)于判定性問題的解釋”（A Note on the Entscheidungsproblem）一文中證明出了一個相似的論題，但是他采用遞歸函數(shù)和Lambda可定義函數(shù)來形式地描述有效可計(jì)算性。Lambda可定義函數(shù)由阿隆佐·邱奇和斯蒂芬·克萊尼（Church 1932, 1936a, 1941, Kleene 1935）提出，而遞歸函數(shù)由庫爾特·哥德爾（Kurt G?del）和雅克·埃爾布朗（Jacques Herbrand，G?del 1934, Herbrand 1932）提出。這兩個機(jī)制描述的是同一集合的函數(shù)，正如邱奇和克林（Church 1936a, Kleene 1936）所展示的正整數(shù)函數(shù)那樣。在聽說了邱奇的建議后，圖靈很快就證明了他的圖靈機(jī)實(shí)際上描述的是同一集合的函數(shù)（Turing 1936, 263ff）。5

20世紀(jì)上半葉，對可計(jì)算性進(jìn)行公式化表示的嘗試有：

美國數(shù)學(xué)家阿隆佐·邱奇創(chuàng)建了稱為λ演算的方法來定義函數(shù)。英國數(shù)學(xué)家阿蘭·圖靈創(chuàng)建了可對輸入進(jìn)行運(yùn)算的理論機(jī)器模型，現(xiàn)在被稱為通用圖靈機(jī)。邱奇以及數(shù)學(xué)家斯蒂芬·科爾·克萊尼和邏輯學(xué)家J. Barkley Rosser一起定義了一類函數(shù)， 這種函數(shù)的值可使用遞歸方法計(jì)算。

這三個理論在直覺上似乎是等價的--它們都定義了同一類函數(shù)。因此，計(jì)算機(jī)科學(xué)家和數(shù)學(xué)家們相信，可計(jì)算性的精確定義已經(jīng)出現(xiàn)。邱奇-圖靈論題的非正式表述說：如果某個算法是可行的，那這個算法同樣可以被圖靈機(jī)，以及另外兩個理論所實(shí)現(xiàn)。

雖然這三個理論被證明是等價的，但是其中的前提假設(shè)--“能夠有效計(jì)算”是一個模糊的定義。因此，雖然這個假說已接近完全，但仍然不能由公式證明。

影響之后用于描述有效計(jì)算的許多其他機(jī)制也被提了出來，比如寄存器機(jī)、埃米爾·波斯特（Emill Post）的波斯特系統(tǒng)，組合子邏輯以及馬爾可夫算法（Markov 1960）等。所有這些體系都已被證明在計(jì)算上和圖靈機(jī)擁有基本相同的能力；類似的系統(tǒng)被稱為圖靈完全。因?yàn)樗羞@些不同的試圖描述算法的努力都導(dǎo)致了等價的結(jié)果，所以現(xiàn)在普遍認(rèn)為邱奇－圖靈論題是正確的。但是，該論題不具有數(shù)學(xué)定理一般的地位，也無法被證明；說是定理不如說是個將可計(jì)算性等同于圖靈機(jī)的提議。如果能有一個方法能被普遍接受為一個有效的算法但卻無法在圖靈機(jī)上允許，則該論題也是可以被駁斥的。6

在20世紀(jì)初期，數(shù)學(xué)家們經(jīng)常使用一種非正式的說法即可有效計(jì)算，所以為這個概念尋找一個好的形式描述也是十分重要的。當(dāng)代的數(shù)學(xué)家們則使用圖靈可計(jì)算（或簡寫為可計(jì)算）這一定義良好的概念。由于這個沒有定義的用語在使用中已經(jīng)淡去，所以如何定義它的問題已經(jīng)不是那么重要了。

哲學(xué)內(nèi)涵邱奇－圖靈論題對于心智哲學(xué)（philosophy of mind）有很多寓意，但是對于該論題的很多哲學(xué)解讀存在曲解。哲學(xué)學(xué)者B. Jack Copeland認(rèn)為關(guān)于圖靈機(jī)是否可模擬確定的物理過程的問題仍沒有得到解答。他進(jìn)一步聲稱關(guān)于這些物理過程是否在人類的智能機(jī)制中起到作用的問題也是未決的。有很多重要而懸而未決的問題也涵蓋了邱奇－圖靈論題和物理學(xué)及超計(jì)算（hypercomputation）的可能性之間的關(guān)系。應(yīng)用到物理學(xué)上，該論題有很多可能的意義：7

宇宙是一臺圖靈機(jī)（由此，在物理上對非遞歸函數(shù)的計(jì)算是不可能的）。該論述被定義為大邱奇－圖靈論題。

宇宙不是一臺圖靈機(jī)（也就是說，物理的定律不是圖靈可計(jì)算的），但是不可計(jì)算的物理事件卻不能阻礙創(chuàng)建超計(jì)算機(jī)（hypercomputer）的可能性。比如，一個在物理上包含實(shí)數(shù)而非可計(jì)算實(shí)數(shù)的宇宙就可以被劃為此類。

宇宙是一臺超計(jì)算機(jī)，而且建造物理設(shè)備來實(shí)現(xiàn)這一特性并以之計(jì)算非遞歸函數(shù)是可能的。比如，一個懸而未決的問題是我們無法確定量子力學(xué)（quantum mechanical）的事件是否圖靈可計(jì)算的，盡管諸如量子圖靈機(jī)之類的嚴(yán)格模型實(shí)際上等價于確定性圖靈機(jī)（但并不一定在效率上等價）。約翰·盧卡斯和名氣更大一點(diǎn)的羅杰·潘洛斯曾經(jīng)建議說人的心靈可能是量子力學(xué)和非算法計(jì)算的結(jié)果， 盡管并沒有科學(xué)證據(jù)支持這一提議。

實(shí)際上在這三類之外或其中還有許多其他的技術(shù)上的可能性，但這三類只是為了闡述這一概念。

不可計(jì)算函數(shù)我們可以正式定義不可計(jì)算的函數(shù)。一個有名的例子是海貍很忙函數(shù)。該函數(shù)接受輸入n，返回具有n個狀態(tài)的圖靈機(jī)在停機(jī)之前所能打印的最大符號數(shù)量。找到海貍很忙函數(shù)的上限等于解決停機(jī)問題，該問題已被確定不能使用圖靈機(jī)解決。由于海貍很忙函數(shù)不能被圖靈機(jī)計(jì)算， 邱奇-圖靈論題斷言該函數(shù)不能使用任何方法進(jìn)行有效計(jì)算。8

有一些模型可用于計(jì)算（邱奇-圖靈）不可計(jì)算函數(shù)：即所謂的超計(jì)算機(jī)。Mark Burgin認(rèn)為類似歸納性圖靈機(jī)的超遞歸算法（super-recursive algorithms）可用于反證邱奇-圖靈論題。他的論述依賴于對算法更廣泛的定義， 這種定義上的擴(kuò)展使得一些歸納性圖靈機(jī)包含的不可計(jì)算函數(shù)變得可計(jì)算。這種對邱奇-圖靈論題的解讀與計(jì)算機(jī)科學(xué)的常規(guī)解讀不同，把超遞歸算法歸于邱奇-圖靈意義上的算法的這種看法并未受到相關(guān)領(lǐng)域的廣泛接受。