《church論題》word版

《《church論題》word版》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、Church論題Church論題2010年05月26日星期三下午09：24在理論計(jì)算機(jī)科學(xué)中，有了可計(jì)算性概念嚴(yán)格的數(shù)學(xué)刻劃，才使證明一系列重要的數(shù)學(xué)問題的算法不可解性成為可能。一個(gè)眾所周知的事實(shí)是，直到1935年著名的"算法可計(jì)算函數(shù)都是遞歸函數(shù)"這一丘奇論題提出，算法可計(jì)算性這個(gè)直觀概念才有了精確的數(shù)學(xué)刻劃。而同樣需要指出的是，哥德爾(K.Gdel)在此之前的1931年就引進(jìn)了原始遞歸函數(shù)概念，1934年明確給出一般遞歸函數(shù)的定義，1934年春還曾與丘奇(A.Church)一起討論如何給"算法可計(jì)算性"下一個(gè)精確的數(shù)學(xué)定義的問題

2、。那么，為什么哥德爾沒有適時(shí)給出丘奇論題，卻對圖靈工作大加贊賞，從而接受丘奇-圖靈論題呢?我們認(rèn)為，其中的最重要原因是，圖靈是完全沿著哥德爾設(shè)想的思路對算法概念給出分析的第一人，圖靈機(jī)概念澄清了形式系統(tǒng)概念的內(nèi)涵；同時(shí)，與波斯特20年代的想法一樣，圖靈論題通過指出機(jī)器能做什么，把計(jì)算系統(tǒng)引入了物理世界，引發(fā)了一場信息革命和心-腦-計(jì)算機(jī)的大論戰(zhàn)。而且圖靈論題揭示了哥德爾認(rèn)識到的，可計(jì)算性是一個(gè)不依賴于形式系統(tǒng)的絕對概念這一事實(shí)。隨著"計(jì)算機(jī)的發(fā)展遵循摩爾定律"這一假說被普遍認(rèn)可，哥德爾對圖靈工作大加贊賞的幾個(gè)因素更加顯示出對計(jì)算機(jī)發(fā)

3、展的理論意義和現(xiàn)實(shí)意義。1980年代人們開始討論如何"超越圖靈計(jì)算"，將算法或計(jì)算這樣的純粹抽象的數(shù)學(xué)概念看作物理定律的體現(xiàn)，把計(jì)算系統(tǒng)看作自然定律的一個(gè)自然結(jié)果。特別是認(rèn)為，丘奇-圖靈論題也同時(shí)斷定了一條物理原理，這就是1985年多奇(D.Deutsch)提出的丘奇-圖靈論題的物理版本(也稱多奇原理)。正是基于這一原理，量子計(jì)算機(jī)的計(jì)算本質(zhì)成為1990年以來人們關(guān)注的熱點(diǎn)。我們認(rèn)為，在當(dāng)今對認(rèn)知科學(xué)中認(rèn)知可計(jì)算主義研究綱領(lǐng)提出質(zhì)疑時(shí)，更有必要澄清關(guān)于丘奇-圖靈論題和多奇原理的內(nèi)涵，也有必要對量子計(jì)算機(jī)的計(jì)算本質(zhì)作出恰當(dāng)?shù)倪壿嫹治觥?/p>

4、1哥德爾為什么沒有提出丘奇論題歷史上，狄特金(R.Dedekind)，皮亞諾(G.Peano)，司寇倫(T.Skolem)，希爾伯特(D.Hilbert)和阿克曼(W.Ackermann)都曾研究過遞歸函數(shù)，但哥德爾是第一個(gè)精確定義這個(gè)概念的。今天我們所稱的"原始遞歸函數(shù)"是哥德爾1931年在那篇劃時(shí)代的論文中引進(jìn)的。1934年2-5月，哥德爾在普林斯頓研究院關(guān)于不完全性結(jié)果的系列講座中又引進(jìn)了一般遞歸函數(shù)概念，指出："一般遞歸函數(shù)(我們現(xiàn)在稱原始遞歸函數(shù))有著重要的特性，即對于每個(gè)給定的自變量值的集合，都能通過有窮程序計(jì)算出函數(shù)值

5、。"具有歷史意謂的是哥德爾還對此補(bǔ)充了一個(gè)頗具建設(shè)性的說明(著名的腳注3)："這個(gè)命題的逆[即每個(gè)通過有窮程序計(jì)算的函數(shù)都是原始遞歸函數(shù)]似乎也是真的，除了[原始]遞歸，…其他形式的遞歸(例如與帶兩個(gè)變量的加法相對應(yīng)的遞歸)是否也是允許的。由于有窮可計(jì)算的概念還沒有定義，目前不可能證明這個(gè)命題的逆，但是，它完全可以充當(dāng)一種助探原則。"[6]哥德爾的這段腳注曾被戴維斯(MartinDavis)認(rèn)為是丘奇論題的一種形式。他甚至以"哥德爾論題"的名稱對其重新做了表述："每個(gè)機(jī)械可計(jì)算函數(shù)都可用一般遞歸函數(shù)定義"。在準(zhǔn)備編進(jìn)《不可判定的》論

6、文集的一篇介紹哥德爾講座的短文中，戴維斯表達(dá)了他的這一見解，并將初稿寄給哥德爾進(jìn)行評價(jià)。完全出乎戴維斯意料的是，哥德爾在回信中對此表達(dá)了不同見解："…說腳注3是丘奇論題的一種陳述是不正確的。我無非是提出了'有窮可計(jì)算程序'與'遞歸程序'是等價(jià)的一種猜想。但在系列講座中我根本沒有料想到，我的遞歸概念包含了所有可能的遞歸。"[3]從這封信中至少我們可以看出，哥德爾1934年春就給出今天意義上的"遞歸函數(shù)"的定義了，但是他完全沒有猜到他當(dāng)時(shí)的定義足夠?qū)?，可以包容所有的遞歸。而且他認(rèn)為，自己對算法可計(jì)算性的猜測(即戴維斯所說的"哥德爾論題"

7、)并不是丘奇論題的等價(jià)說法，但它可以充當(dāng)一種助探原則，幫助人們尋求算法可計(jì)算性概念的一個(gè)令人滿意的數(shù)學(xué)刻劃。2從l可定義性到丘奇論題丘奇是在1935年4月美國數(shù)學(xué)會的一次報(bào)告中宣布他的論題的。事實(shí)上，丘奇最早關(guān)注可計(jì)算性是從l可定義性概念著手的。據(jù)當(dāng)年丘奇的學(xué)生克林尼(S.C.Kleene)的說法，到了1933年，丘奇的"l可定義性"已經(jīng)作為一個(gè)成熟的概念在普林斯頓的邏輯學(xué)家中流傳。他當(dāng)時(shí)猜測，l可定義函數(shù)就是算法可計(jì)算函數(shù)，并最終提出這一論題。后來，克林尼曾回憶說："當(dāng)丘奇提出這一論題時(shí)，我準(zhǔn)備用對角化方法否證它，希望指出算法可計(jì)

8、算函數(shù)超出了l可定義函數(shù)類。但是我很快認(rèn)識到做不到這一點(diǎn)。于是，一夜之間我成了丘奇這個(gè)論題的支持者。"[9]據(jù)戴維斯考察，盡管丘奇1933-1934年明顯對可計(jì)算性概念懷有濃厚興趣，但直到哥德爾作普林斯頓系列講座之前，沒有明顯的跡象表