《計算的極限》系列

殊途同歸

大洋彼岸寄來的論文，對于圖靈來說，并不是什么好消息。在看到丘奇的論文后，圖靈有過何等反應(yīng)，至今恐怕已不可考。面對著一位在數(shù)理邏輯方面已然小有名氣的職業(yè)數(shù)學(xué)家，與自己一起獨立發(fā)現(xiàn)了相同的突破性結(jié)果。往好處想，這說明圖靈自己的水平已經(jīng)達(dá)到了當(dāng)時數(shù)理邏輯研究的前沿；往壞處想，重復(fù)了別人的結(jié)果，哪怕是獨立發(fā)現(xiàn)的，似乎都有些不對味兒。

然而，在下定論之前，圖靈還有一件事情要搞清楚。他和丘奇對“可計算性”的定義，分別建筑在圖靈機(jī)與λ演算之上。那么，在不同的基礎(chǔ)上定義的兩種“可計算性”，是貌合神離還是本為一體？

圖靈機(jī)與λ演算，兩者似乎都在平平無奇中暗藏玄機(jī)。作為計算模型，它們有很多相似之處，比如自我指涉的能力。但它們看起來又是如此不同，圖靈機(jī)是一臺在工程上能建造的機(jī)器，而λ演算則是一個徹頭徹尾的數(shù)學(xué)模型?？雌饋恚卮疬@個問題，并非易事。

圖靈知道，丘奇也知道，他們已經(jīng)踏入了一個新領(lǐng)域。昔日希爾伯特在他的二十三個問題中，一語帶過的那個“機(jī)械化的運算”，即將被賦予精確的數(shù)學(xué)含義。但正因如此，踏出的第一步必須慎之又慎，尤其對于“可計算性”這個最基礎(chǔ)的定義，必須做到毫不含糊。為此，為了消除模棱兩可之處，圖靈機(jī)與λ演算是否能力相當(dāng)，這是個必須回答的問題。

知己知彼，百戰(zhàn)不殆。為了解答這個問題，圖靈開始鉆研λ演算，試圖弄清到底λ演算能計算什么。終于，他證明了，所有λ演算能計算的函數(shù)，他的圖靈機(jī)也能計算，反之亦然。也就是說，λ演算與圖靈機(jī)的計算能力是等價的，兩種模型定義的“可計算性”實際上殊途同歸。他將這個結(jié)果作為附錄補(bǔ)充到了他的論文。

對于圖靈來說，這既是個壞消息，也是個好消息。壞消息是，他的結(jié)果與丘奇的重復(fù)了，對于發(fā)表文章來說，這不是什么好事情。好消息是，他的結(jié)果與丘奇的重復(fù)了，但他對可計算性的定義與丘奇的截然不同，而且兩種看似毫無關(guān)系的定義，在實質(zhì)上是相同的，這說明，他們對可計算性的定義，這最初的一步踏出的方向是正確的。一個人提出的定義很可能忽視某個方面，但現(xiàn)在兩個截然不同的定義引向相同的結(jié)果，在交叉印證下，幾無出錯之虞。

可以說，圖靈的工作面世之日，正是可計算性理論呱呱墜地之時。

也難怪紐曼教授一開始不相信圖靈的工作。僅僅二十出頭，剛剛踏入科學(xué)界的年輕人，就解決了如此重要的問題，而且為一個全新的領(lǐng)域立下了奠基石，這種人，即使在劍橋這個英國頂尖學(xué)府，也可謂難得一見。倒不如說，一開始不相信，這才是正常的反應(yīng)。

但即便不相信，數(shù)學(xué)證明就是證明。即使紐曼教授并不專精于數(shù)理邏輯，還是能看出圖靈論文的過人之處。他決定為圖靈爭取發(fā)表的機(jī)會。

這并非易事。因為從結(jié)論上說，圖靈重復(fù)了丘奇的結(jié)果，所以最初聯(lián)系的幾個期刊的編輯都婉拒了紐曼的要求：他們只看到了論文的結(jié)論，沒看到論文的精髓。最后，紐曼找到了當(dāng)時倫敦皇家學(xué)會學(xué)報的編輯，經(jīng)過三催四勸，終于說服編輯發(fā)表圖靈的文章。

《論可計算數(shù)，及其在可判定性問題上的應(yīng)用》，圖靈的這篇文章，后來被認(rèn)為是倫敦皇家學(xué)會學(xué)報發(fā)表過的最重要的文章之一。

萬變之宗

乘著遠(yuǎn)洋貨輪，圖靈的論文很快傳到了大洋彼岸，在普林斯頓掀起了一陣旋風(fēng)。

在普林斯頓高等研究院的哥德爾，與丘奇有過不少碰面的機(jī)會。他讀過丘奇的論文，大概也聽過丘奇本人介紹他的λ演算。但哥德爾對λ演算一直頗有微詞。實際上，作為一種計算模型，λ演算從未得到他的認(rèn)可。它與人們?nèi)粘＝佑|到的“計算”毫無相似之處，更像是符號的堆砌和推演。雖然其中的計算的確可以機(jī)械性地完成，但要證明這一點絕非易事。事實上，這是一個遠(yuǎn)非顯然的定理，證明也相當(dāng)復(fù)雜。總而言之，λ演算并不像機(jī)械的計算，更像智慧的推理。

實際上，哥德爾自己也有一套“機(jī)械計算”的模型，那正是他在證明哥德爾不完備性定理時發(fā)展出來的遞歸函數(shù)體系。這套體系將“機(jī)械計算”定義為遞歸函數(shù)能計算的內(nèi)容，而遞歸函數(shù)，顧名思義，就是可以用某些遞歸方式定義的整數(shù)函數(shù)。但哥德爾對他自己的模型同樣不滿意，原因同樣是他的模型似乎需要太多的聰明才智，不像一臺機(jī)器。

但圖靈的論文瞬間就令哥德爾為之折服。

任何人，只要看一眼圖靈機(jī)的定義，都會認(rèn)同圖靈機(jī)的計算完全是機(jī)械演算，完全可以造出一臺可以運作的實際的圖靈機(jī)。而更重要的是，圖靈機(jī)抓住了“機(jī)械計算”的神韻。

機(jī)械計算是什么？是機(jī)器可以做出的計算。但機(jī)器可以千奇百怪，要用三言兩語抓住本質(zhì)，似乎不太可能。那么，何不反其道而行之？與其想像這些機(jī)器共有的特性，不如尋找它們共有的限制。

這正是圖靈在論文中的做法。他總結(jié)了以下幾個機(jī)器計算的限制：

第一：一臺機(jī)器只有有限個可以分辨的狀態(tài)；一臺機(jī)器能分辨的表示數(shù)據(jù)的符號只有有限種。

開關(guān)或開或合，電路或通或斷，中間的變化是跳躍式的。即使是連續(xù)的電信號，由于不可避免的熱噪聲影響，通過測量能分辨出的狀態(tài)同樣只有有限個。雖然現(xiàn)代的計算機(jī)看似有無限可能，但這只是幻覺。CPU和內(nèi)存中的電路，數(shù)量雖然龐大無比，但總歸是有限的，它們的通斷形成的不同狀態(tài)亦是如此。同理，雖然符號、信號在細(xì)節(jié)上可以有無數(shù)種變化，但由于精度等問題，即使是人，也無法事無巨細(xì)將所有細(xì)節(jié)一一分辨出來，更何況機(jī)器。

第二：機(jī)器的每一步操作需要的時間有一個下限，而每次操作最多只能讀入與改寫外部有限個符號。在某次操作讀寫某處的符號后，下一步機(jī)器讀寫的符號與之前符號的距離應(yīng)該是有界的。

由于物理的限制，不存在速度無限的物體。無論任何機(jī)器，都不能在有限的時間內(nèi)作出無限次操作，當(dāng)然也不可能有無限次讀入與改寫。同樣，讀寫頭移動的速度是有限的，所以兩次操作讀寫符號的距離當(dāng)然也有限制。

第三：在某步操作中，機(jī)器的行動完全取決于它當(dāng)時的內(nèi)部狀態(tài)以及讀取到的符號。

機(jī)器就是機(jī)器，它應(yīng)該做的，就是按照預(yù)先規(guī)劃的圖紙一步一步執(zhí)行。沒有異想天開，沒有靈光一現(xiàn)，只有照章辦事，只有步步為營。

這幾個限制看起來相當(dāng)合理，甚至顯得理所當(dāng)然。但就從如此平平無奇的限制出發(fā)，圖靈用縝密的邏輯說明了，一臺服從這些限制的機(jī)器能計算的問題，必定可以用一臺特定的圖靈機(jī)解決。也就是說，任何一臺服從這些限制的機(jī)器，無論設(shè)計如何精巧，構(gòu)成如何復(fù)雜，它的計算能力都不可能超越圖靈機(jī)，無一例外。

我們甚至可以說，圖靈機(jī)的設(shè)計本身，正是這些限制的一種體現(xiàn)。圖靈很可能一開始就意識到了這些限制，再由此出發(fā)，去定義他的圖靈機(jī)。哥德爾之所以對圖靈機(jī)擊節(jié)嘆賞，大概也正因蘊含在它定義中的，圖靈對“機(jī)械計算”的深刻洞察。相比之下，雖然與之等價的λ演算也尚算精致，但對于“機(jī)械計算”只得其形未得其神，顯然遜色不少。

現(xiàn)在，希爾伯特在他的問題中那模糊的“機(jī)械計算”，終于有了一個精確的定義：機(jī)械計算，就是圖靈機(jī)能做的計算。這又被稱為圖靈-丘奇論題，正是可計算性理論的奠基石。

除了λ演算與遞歸函數(shù)以外，還有許多計算系統(tǒng)與圖靈機(jī)等價。波斯特對應(yīng)問題，計數(shù)器機(jī)，馬爾可夫算法，甚至元胞自動機(jī)，這些計算模型都與圖靈機(jī)等價。但以我們的后見之明來看，圖靈機(jī)仍然是機(jī)械計算最自然最有用的模型之一。

也正因這篇論文，圖靈得到了到普林斯頓讀博深造的機(jī)會，在丘奇的指導(dǎo)下，得以繼續(xù)探索可計算性的無限可能。在大洋彼岸等待圖靈的，又是可計算性理論的一篇新章。

計算的極限（三）：函數(shù)構(gòu)成的世界 計算的極限（零）：邏輯與圖靈機(jī) 計算的極限（二）：自我指涉與不可判定 計算的極限（一）：所有機(jī)器的機(jī)器，與無法計算的問題 RSA算法原理（二）