在理論計算機科學中，有了可計算性概念嚴格的數學刻劃，才使證明一系列重要的數學問題的算法不可解性成為可能。一個眾所周知的事實是，直到1935年著名的“算法可計算函式都是遞歸函式”這一丘奇論題提出，算法可計算性這個直觀概念才有了精確的數學刻劃。
基本介紹
- 中文名：丘奇定理
- 外文名：Church
- 提出者：丘奇
- 提出時間：1935年
- 套用學科：理論計算機科學
- 適用領域範圍：理論計算機科學
丘奇定理,邏輯分析,哥德爾為什麼沒有提出丘奇論題,從l可定義性到丘奇論題,哥德爾為什麼讚賞圖靈論題,
丘奇定理
而同樣需要指出的是，哥德爾(K.Gödel)在此之前的1931年就引進了原始遞歸函式概念，1934年明確給出一般遞歸函式的定義，1934年春還曾與丘奇(A.Church)一起討論如何給“算法可計算性”下一個精確的數學定義的問題。那么，為什麼哥德爾沒有適時給出丘奇論題，卻對圖靈工作大加讚賞，從而接受丘奇-圖靈論題呢？
我們認為，其中的最重要原因是，圖靈是完全沿著哥德爾構想的思路對算法概念給出分析的第一人，圖靈機概念澄清了形式系統概念的內涵；同時，與波斯特20年代的想法一樣，圖靈論題通過指出機器能做什麼，把計算系統引入了物理世界，引發了一場信息革命和心-腦-計算機的大論戰。而且圖靈論題揭示了哥德爾認識到的，可計算性是一個不依賴於形式系統的絕對概念這一事實。
隨著“計算機的發展遵循摩爾定律”這一假說被普遍認可，哥德爾對圖靈工作大加讚賞的幾個因素更加顯示出對計算機發展的理論意義和現實意義。1980年代人們開始討論如何“超越圖靈計算”，將算法或計算這樣的純粹抽象的數學概念看作物理定律的體現，把計算系統看作自然定律的一個自然結果。特別是認為，丘奇-圖靈論題也同時斷定了一條物理原理，這就是1985年多奇(D.Deutsch)提出的丘奇-圖靈論題的物理版本(也稱多奇原理)。正是基於這一原理，量子計算機的計算本質成為1990年以來人們關注的熱點。我們認為，在當今對認知科學中認知可計算主義研究綱領提出質疑時，更有必要澄清關於丘奇-圖靈論題和多奇原理的內涵，也有必要對量子計算機的計算本質作出恰當的邏輯分析。
邏輯分析
哥德爾為什麼沒有提出丘奇論題
歷史上，狄特金(R.Dedekind)，皮亞諾(G.Peano)，司寇倫(T.Skolem)，希爾伯特(D.Hilbert)和阿克曼(W.Ackermann)都曾研究過遞歸函式，但哥德爾是第一個精確定義這個概念的。今天我們所稱的“原始遞歸函式”是哥德爾1931年在那篇劃時代的論文中引進的。1934年2-5月，哥德爾在普林斯頓研究院關於不完全性結果的系列講座中又引進了一般遞歸函式概念，指出：
“一般遞歸函式(我們現在稱原始遞歸函式)有著重要的特性，即對於每個給定的自變數值的集合，都能通過有窮程式計算出函式值。”
具有歷史意謂的是哥德爾還對此補充了一個頗具建設性的說明(著名的腳註3)：
“這個命題的逆[即每個通過有窮程式計算的函式都是原始遞歸函式]似乎也是真的，除了[原始]遞歸，…其他形式的遞歸(例如與帶兩個變數的加法相對應的遞歸)是否也是允許的。由於有窮可計算的概念還沒有定義，目前不可能證明這個命題的逆，但是，它完全可以充當一種助探原則。”[6]
哥德爾的這段腳註曾被戴維斯(Martin Davis)認為是丘奇論題的一種形式。 他甚至以“哥德爾論題”的名稱對其重新做了表述:
“每個機械可計算函式都可用一般遞歸函式定義”。
在準備編進《不可判定的》論文集的一篇介紹哥德爾講座的短文中，戴維斯表達了他的這一見解，並將初稿寄給哥德爾進行評價。完全出乎戴維斯意料的是，哥德爾在回信中對此表達了不同見解：
“… 說腳註3是丘奇論題的一種陳述是不正確的。我無非是提出了‘有窮可計算程式’與‘遞歸程式’是等價的一種猜想。但在系列講座中我根本沒有料想到，我的遞歸概念包含了所有可能的遞歸。”[3]
從這封信中至少我們可以看出，哥德爾1934年春就給出今天意義上的“遞歸函式”的定義了，但是他完全沒有猜到他當時的定義足夠寬，可以包容所有的遞歸。而且他認為，自己對算法可計算性的猜測(即戴維斯所說的“哥德爾論題”)並不是丘奇論題的等價說法，但它可以充當一種助探原則，幫助人們尋求算法可計算性概念的一個令人滿意的數學刻劃。
從l可定義性到丘奇論題
丘奇是在1935年4月美國數學會的一次報告中宣布他的論題的。事實上，丘奇最早關注可計算性是從l可定義性概念著手的。據當年丘奇的學生克林尼(S.C.Kleene)的說法，到了1933年，丘奇的“l可定義性”已經作為一個成熟的概念在普林斯頓的邏輯學家中流傳。他當時猜測，l可定義函式就是算法可計算函式，並最終提出這一論題。後來，克林尼曾回憶說：
“當丘奇提出這一論題時，我準備用對角化方法否證它，希望指出算法可計算函式超出了l可定義函式類。但是我很快認識到做不到這一點。於是，一夜之間我成了丘奇這個論題的支持者。”[9]
據戴維斯考察，儘管丘奇1933-1934年明顯對可計算性概念懷有濃厚興趣，但直到哥德爾作普林斯頓系列講座之前，沒有明顯的跡象表明他認為算法可計算性與某種嚴格的數學概念相一致，也沒有相關的什麼特別的說法。也許正是在1934年2-5月與哥德爾討論之後，他才形成了明確的見解，並給出後來的丘奇論題的。1935年11月29日，在給克林尼的一封信中，丘奇則對此曾給出了一個多少含糊其詞的說法：
“談及哥德爾、遞歸函式和算法可計算性概念，這段歷史原本是這樣的。在與哥德爾討論l可定義性概念時，我們發現對於算法可計算性找不到一個好的定義，我建議，可以用l可定義性充當定義，但是哥德爾認為完全不合適。我回答說，如果你能提供任何一個，哪怕是部分令人滿意的定義，我都將證明它一定包含在l可定義性概念之中。當時哥德爾唯一的想法是，先將算法可計算性當作一個不確定概念，陳述能描述這個概念公認特性的公理集合，然後在此基礎上再去做其他事情。顯然，後來他認為，可以對厄爾布朗(J.Herbrand)建議的遞歸函式概念沿著可計算性概念的方向加以修正。他特別指出，可以在這個意義上將遞歸和算法可計算性二者聯繫起來。但是，他又說，他並不認為這兩個概念能夠令人滿意地被確認是彼此一致的，除非是在一種助探的意義上。”[3]
當1935年丘奇向數學界宣布他的論題時，他是如下表達的：“採納厄爾布朗的建議，並在一個重要方面作了修正，哥德爾在1934年的系列講座中提出了遞歸函式的定義，這裡採取的基本上是哥德爾關於正整數遞歸函式的定義，而且需要強調的是，正整數的算法可計算函式將被確定為與遞歸函式一致。由於其他關於算法可計算性的似真定義原本都是導出概念，因此它們或者與遞歸性等價，或者比遞歸性弱。”[3]
顯然，丘奇沒有選擇用“l可定義”的術語陳述他的論題，而是使用了“厄爾布朗-哥德爾一般遞歸函式”的術語。在這裡，l可定義性隱含地劃在了“其他算法可計算性的似真定義”中了。這種措辭給人的印象是，1935年春，丘奇還沒有認定，l可定義性與厄爾布朗-哥德爾一般遞歸是等價的。直到1936年4月，丘奇在《初等數論中的一個不可解問題》中才斷定l可定義性函式就是一般遞歸函式。
在1936年的論文中，丘奇給出了如今我們所知的丘奇論題的標準陳述：“現在我們通過與正整數的遞歸函式(或者正整數的l可定義函式)概念相一致，來定義已經討論過的正整數的算法可計算的概念。這個選出的與直觀的可計算性概念相符的定義被認為是已經核證了的。”[1]
這裡，丘奇把算法可計算性與遞歸性之間的這種等價稱為“定義”，波斯特(E.Post)1936年曾極力反對定義的提法，認為應當僅僅作為一種工作假說看待 。1943年克林尼指出，描述這種等價性的命題包含了很強的工作假說的特徵，儘管我們確有不得不相信它的充足理由，因此，建議用“論題”的術語表達這個命題。
儘管提出了丘奇論題，但哥德爾當時並不贊成可計算性與遞歸性或l可定義性等價的說法。在他看來，在還沒有找到一組公理刻划算法可計算性概念所包含的公認特性之前，不可能有完全令人滿意的嚴格的數學定義。直到1936年圖靈(A.Turing)的結果公布時，哥德爾才承認這個困難已經克服。
哥德爾為什麼讚賞圖靈論題
我們認為，正是由於1934-1936年，丘奇、克林尼和哥德爾等人對於可計算性概念的數學刻劃做了一系列工作，最終丘奇提出了他的標準形式的丘奇論題。同時在此期間，圖靈完全獨立於普林斯頓數學家思考可計算性問題，最終以通用圖靈機概念刻劃了算法可計算性，即“算法可計算的就是通用圖靈機可實現的”。它可表達為如下“圖靈論題”：
“每個算法可在一台通用圖靈機上程式化。”
哥德爾在1965年發表的普林斯頓講座筆記(1934)的後記中，對圖靈的工作給予了極高的評價，我們認為，哥德爾不接受丘奇論題，而讚賞圖靈論題的主要原因至少有幾點：
(1) 通用圖靈機概念澄清了形式系統概念
可以說，在哥德爾證明不完全性定理時，形式系統還是一個相當模糊的概念，否則哥德爾會採取更加簡潔的方式證明自己的定理。正是有了圖靈機概念，才使形式系統的特性更加清晰準確地為人們所把握，形式系統不過是一種產生定理的機械程式，圖靈機的工作程式正是數學家在形式系統中實際工作的程式。或者說，形式系統不過是一台準許在某些步驟上按照預定範圍作出選擇的圖靈機。當然，也正是由於有了圖靈機概念，哥德爾關於數學形式系統的不完全性定理才有了各種用圖靈機程式代替形式系統的版本，如停機問題版本以及後來的算法資訊理論中的複雜性版本等。[10]
(2) 圖靈是沿著最貼近哥德爾構想的研究進路作出結論的
丘奇的工作儘管精道優雅，但他完全基於純粹的數學分析；圖靈的分析不僅僅局限於數學形式世界，它是值得稱道的哲學套用的實例。[3]而且，圖靈是沿著最貼近哥德爾構想的研究進路作出結論的。 哥德爾曾評價說，“圖靈的工作對於‘機械程式’(也稱‘算法’,‘計算程式’或‘組合程式’)概念給出了一種分析，指明這個概念是與‘圖靈機’等價的”。而先前給出的其他關於可計算性的等價定義，“無論如何很少適合我們最初的目的”。[2]
那么，哥德爾所說的“最初目的”是什麼？顯然，是他一直主張的，“先將算法可計算性當作一種不定義概念，給出能夠描述這個概念公認特性的公理集，在此基礎上再做某些事情”，在他看來，這才是尋求可計算性嚴格的數學刻劃的真正途徑。儘管圖靈並沒有在任何形式化的意義上採用公理化方法處理問題，但是他指明了，“算法可計算性公認的特性”必然導致一個確定的函式類，這個函式類是可以精確定義的，圖靈給出的清晰準確表達了機械程式概念的圖靈機是指產生部分遞歸函式，而不是指產生一般遞歸函式的圖靈機。因此，在哥德爾那裡，圖靈才是給出準確概念與直觀概念相符的令人信服的理由的第一人，用“可在圖靈機上程式化”或“圖靈機可實現”這個鮮明概念對算法可計算性的刻劃，既是正確的，又是唯一符合我們最初目的的。
(3) 圖靈機可計算概念揭示了可計算性是一個不依賴於形式系統的事實
為了使我們進一步看出，為什麼圖靈的工作對於哥德爾有如此重要的意義，還應當考察哥德爾對於絕對可計算性概念的理解。1935年6月19日，哥德爾在維也納大學報告“論證明長度”，提到所謂“加速定理”。[7]定理的嚴格陳述用到“在一個形式系統S中一個函式φ(x)是可計算的”這個概念，它是指對每個數m，都存在相應的數n，使φ(m)= n在系統中是可證的。對於滿足每一個系統都比前一個系統更強的形式系統的序列S1,S2,…，稱一個函式在Si中是可計算的，是指它是依賴於i的。
在這次報告中，哥德爾附加了關於“絕對可計算性”的一個說明：“可以指出，在形式系統之一的Si中可計算，甚至在一個超窮類型中可計算的一個函式,在 S1中已經是可計算的。因此，在某種確定的意義上，‘可計算’的概念是‘絕對的’，而現實中所有其他熟知的元數學概念(如可證,可定義)等，卻完全是依賴於給定系統的。”
哥德爾在這種“絕對的”意義上認識可計算性大致是在1934-1935年，在1946年《關於數學問題的普林斯頓200周年紀念會感言》中，哥德爾又特彆強調了這種“絕對性”的意義：
“在我看來，一般遞歸或圖靈機可計算這個概念的極端重要性似乎極大地歸於這樣一個事實，即有了這個概念，就第一次成功地給出有意義的認識論觀念上的一種絕對的定義，即可計算性不依賴於形式系統的選擇。但在所有先前處理的其他情形下，例如，像定義可判定性或可定義性時，都要依賴於給定的語言。儘管絕對可計算性也不過是特殊種類的可判定性概念，但情形已與過去完全不同。”[8]
(4) 圖靈機概念把一個計算系統引入了物理世界
另一個值得哥德爾稱道圖靈工作的原因恐怕就是，同波斯特20年代曾經有過的想法一樣，圖靈通過指出計算機器能做什麼，把一個計算系統引入物理世界，或者說，把一個是否可計算的問題轉換成了一個物理上是否可實現的問題，引發了一場信息革命和心-腦-計算機的大論戰。圖靈實際上指出了，凡是可形式化描述並可以算法化的東西，都可以找到作為通用圖靈機特例的計算機迅速準確地處理，這一原理開啟了人類智慧型的機器模擬的新紀元。正如圖靈在《可計算數》一文中所講的，他本人研究可計算性的動機不僅僅在形式上，而在於“心智科學”上。哥德爾甚至直到晚年仍不減探討由圖靈提出的心靈-大腦-計算機的話題的興趣，恐怕也表明他對於心智科學情有所鐘。
5 丘奇-圖靈論題的物理版本與量子計算機的計算本質
哥德爾讚賞圖靈工作的幾個因素，恰是現代理論計算機發展的基礎和動力所在。當第一台通用電子計算機這種物理裝置誕生後，人們真正看到了通用圖靈機的物理實現(雖然沒有無限存儲)。從此，人們開始思考，實在世界本身是可計算的嗎？模擬客觀實在的理想模擬機器原則上究竟是物理可實現的，還是客觀世界完全超出了通用圖靈機所模擬的範疇？對此，相當一部分物理學家抱有樂觀態度。1985年，牛津大學的多奇教授甚至引進了一個頗具啟發的“丘奇-圖靈論題的物理版本”，將“能行可計算的函式”替換為“有限可實現的物理系統”，陳述了他的所謂“多奇原理”(也稱“物理的丘奇-圖靈原理”)：“每個有限可實現的物理系統，總能為一台通用模擬機器以有限方式的操作來完美地模擬”[4]。我們知道，基於現代物理學和生物物理學，許多物理學家認為，從巨大的天體到我們的生命體，直至人類心靈，都是有限可實現的物理系統的子系統，因此，依多奇之見，原則上都可以用通用計算機以有限方式的操作完美的模擬。
顯然，多奇原理是較丘奇-圖靈論題更強的“工作假說”，從丘奇-圖靈論題到多奇原理，我們的可計算疆域在不斷拓展。如果多奇原理是正確的，它將揭示出物理實在的深刻本質。這種基於物理主義和可計算主義的立場也恰是人工智慧專家奉行的各種工作假說的核心。多奇等人完全將算法或計算這樣的純粹抽象的數學概念看成了物理定律的體現，把計算系統看成了自然定律的一個自然結果，在他們看來，通用計算機的概念不僅為自然規律所認可，而且很可能就是自然規律的內在要求。事實上，我們知道，所有倡導虛擬現實技術、人工生命、人工智慧的人都相信多奇原理的真理性。當然也沒有任何有力的科學證據能夠反駁多奇原理，因為它是一個包含“通用模擬機器”概念的全稱命題，原則上通用模擬機器可實現的算法(程式)數目是無限的。
依照理論計算機的最新進展，量子計算機的倡導者斷言，能夠實現多奇原理的通用模擬機器只能是量子通用圖靈機。1998年作為“量子領域旗手”的傑拉德·密爾本(G.L.Milburn)指出，物理理論與物理版本的丘奇-圖靈論題密切相關的事實是，物理理論是通過數學給出觀察數據的，這些數據正是那些被我們稱作可計算問題所提供的數據，因此這些數據可通過在一台通用圖靈機上運行的算法得到。無論是經典的還是量子的物理系統都可以任意高的精度模擬，然而對某些問題，運行程式的時間可能是一個天文數字。如果世界是經典的，可以用蒙特卡羅方法等有效模擬隨機性；但如果世界是具有不可約隨機性的量子的，就不能用基於隱變數的經典隨機性來解釋量子隨機性，量子世界的遊戲需遵循費曼規則。因此費曼(R.Feynmen)意識到，解決這一問題的方法是建造一種量子計算機，即利用量子過程本身作為計算手段，計算的基本步驟將在原子或亞原子水平上進行，於是，1998年，丘奇-圖靈論題經多奇原理，又被修正成：
“所有有限可描述的物理測量系統的結果都可以很好地為一台通用量子計算機以有限方式的操作完美地模擬，測量結果的記錄是最終產物。”
這裡的“有限可描述的物理測量系統” 是指建立和操縱一個測量裝置的指令必須能夠用有限的代碼來表達；“完美的模擬”是指，模擬產生的數據與真實測量所得的數據無法區分；“最終產物”是指所有的模擬測量必須在某一時刻結束，不再繼續產生新結果。
那么量子計算機超越經典計算機之處何在？它的計算本質究竟為何？
首先，量子計算機可以完成經典計算機所不能完成的計算：例如，它可以任意的精確度模擬一個量子物理系統，可使求解時間不隨問題的規模呈指數增長。例如，以往要完成一個64位數字分解成質因數的乘積的運算，即使是使用超級計算機也要花比宇宙年齡還要長的時間。而貝爾實驗室的彼德·肖爾(Peter Shor)的量子算法，依賴於大尺度的量子糾纏，可在量子計算機上以相當短的時間內成功地將一個64位數字分解成質因數的乘積。量子計算機所以具有超出經典圖靈機的能力，在於量子相干性產生的並行計算的威力。
量子計算機是一個實現計算的物理裝置，是遵循量子物理學規律運行的物理系統，而且量子計算機是一種建立在量子圖靈機基礎上的現代計算機。通用圖靈機的算法是完全確定性的，在這種確定性算法中，當圖靈機的當前讀寫頭的狀態和當前存儲單元內容給定時，下一步的狀態及讀寫頭的運動完全確定。在經典的機率算法中，當前讀寫頭的狀態和當前存儲單元內容給定時，圖靈機以一定的機率變換到下一個狀態及完成讀寫頭的運動。這個機率函式是取值[0，1]的實數，它完全決定了機率圖靈機的性質。量子計算機與經典機率圖靈機的區別僅僅在於當前讀寫頭的狀態和當前存儲單元內容由經典的正交態(0，1)變成了量子態(0，1，0和1的幾率迭加態)，而機率函式則變成了取值為複數的機率振幅函式，於是量子計算機的性質由機率振幅函式確定。量子計算機能作到高效的計算，完全得益於量子迭加效應，即一個原子的狀態可處於0和1的幾率迭加態。一般來講，採用L個量子位，量子計算機可以一次同時對2L個數進行處理，相當於一步計算完成通常經典計算機2L個數的計算。量子計算機就是以量子態對應於計算機的數據和程式(這需要以量子比特取代經典比特)，讀寫頭不同的物理狀態由量子物理描述，機器的動力學機制也由量子物理決定，當然一個更為重要的問題是，我們還必須描述它的輸出，而我們最後需要的又是經典比特，而不是量子比特，這就要解決棘手的“消相干性”。
但是，我們必須清楚地認識到，無論量子計算機的速度有多快，既然從理論上講，量子計算機不過是一台量子圖靈機，那么它就必然受到哥德爾定理所設定的邏輯極限的限制，量子計算機不能計算不可計算的函式，也不能解決停機問題。說到底，量子計算機的計算本質上依然是圖靈機計算，即遞歸函式計算，因此丘奇-圖靈論題依然是量子計算機的理論基礎。多奇試圖將整個物理世界納入計算的範圍，試圖以量子計算機模擬人類智慧型仍然不能擺脫邏輯固有的極限。如果可計算性如哥德爾所言，是不依賴於形式系統的絕對概念，那么量子計算機也不過是另一個計算速度更快的計算載體而已。
值得思考的是，對計算技術的不懈追求是否能使我們切實在程式中捕獲一個真實的 “一致而完備的”世界？[11]在為大自然中的問題提供一個科學解答過程中是否不存在任何邏輯障礙？除了圖靈機之外，是否存在其他計算模型，比如DNA計算機等，人類心智是否可能是某種超越圖靈機的機器？多奇原理告訴我們，不僅物理學決定了計算機能做什麼，而且反過來，計算機能做什麼，也將決定物理定律最終的性質，多奇原理的本意顯然絕不局限於對計算載體進行變革的意義，而在於指出，真實世界 = 物理世界 = 計算世界。
