計(jì)算無處不在。
走進(jìn)一個(gè)機(jī)房，在服務(wù)器排成的一道道墻之間，聽著風(fēng)扇的鼓噪，似乎能嗅出0和1在CPU和內(nèi)存之間不間斷的流動(dòng)。從算籌算盤，到今天的計(jì)算機(jī)，我們用作計(jì)算的工具終于開始量到質(zhì)的飛躍。計(jì)算機(jī)能做的事情越來越多，甚至超越了它們的制造者。上個(gè)世紀(jì)末，深藍(lán)憑借前所未有的搜索和判斷棋局的能力，成為第一臺(tái)戰(zhàn)勝人類國(guó)際象棋世界冠軍的計(jì)算機(jī)，但它的勝利仍然仰仗于人類大師賦予的豐富國(guó)際象棋知識(shí)；而僅僅十余年后，Watson卻已經(jīng)能憑借自己的算法，先“理解”問題，然后有的放矢地在海量的數(shù)據(jù)庫(kù)中尋找關(guān)聯(lián)的答案。長(zhǎng)此以往，工具將必在更多的方面超越它的制造者。而這一切，都來源于越來越精巧的計(jì)算。
計(jì)算似乎無所不能，宛如新的上帝。但即使是這位“上帝”，也逃不脫邏輯設(shè)定的界限。
第一位發(fā)現(xiàn)這一點(diǎn)的，便是圖靈。
《計(jì)算的極限》系列
大洋彼岸寄來的論文，對(duì)于圖靈來說，并不是什么好消息。在看到丘奇的論文后，圖靈有過何等反應(yīng)，至今恐怕已不可考。面對(duì)著一位在數(shù)理邏輯方面已然小有名氣的職業(yè)數(shù)學(xué)家，與自己一起獨(dú)立發(fā)現(xiàn)了相同的突破性結(jié)果。往好處想，這說明圖靈自己的水平已經(jīng)達(dá)到了當(dāng)時(shí)數(shù)理邏輯研究的前沿；往壞處想，重復(fù)了別人的結(jié)果，哪怕是獨(dú)立發(fā)現(xiàn)的，似乎都有些不對(duì)味兒。
然而，在下定論之前，圖靈還有一件事情要搞清楚。他和丘奇對(duì)“可計(jì)算性”的定義，分別建筑在圖靈機(jī)與λ演算之上。那么，在不同的基礎(chǔ)上定義的兩種“可計(jì)算性”，是貌合神離還是本為一體？
圖靈機(jī)與λ演算，兩者似乎都在平平無奇中暗藏玄機(jī)。作為計(jì)算模型，它們有很多相似之處，比如自我指涉的能力。但它們看起來又是如此不同，圖靈機(jī)是一臺(tái)在工程上能建造的機(jī)器，而λ演算則是一個(gè)徹頭徹尾的數(shù)學(xué)模型。看起來，要回答這個(gè)問題，并非易事。
圖靈知道，丘奇也知道，他們已經(jīng)踏入了一個(gè)新領(lǐng)域。昔日希爾伯特在他的二十三個(gè)問題中，一語帶過的那個(gè)“機(jī)械化的運(yùn)算”，即將被賦予精確的數(shù)學(xué)含義。但正因如此，踏出的第一步必須慎之又慎，尤其對(duì)于“可計(jì)算性”這個(gè)最基礎(chǔ)的定義，必須做到毫不含糊。為此，為了消除模棱兩可之處，圖靈機(jī)與λ演算是否能力相當(dāng)，這是個(gè)必須回答的問題。
知己知彼，百戰(zhàn)不殆。為了解答這個(gè)問題，圖靈開始鉆研λ演算，試圖弄清到底λ演算能計(jì)算什么。終于，他證明了，所有λ演算能計(jì)算的函數(shù)，他的圖靈機(jī)也能計(jì)算，反之亦然。也就是說，λ演算與圖靈機(jī)的計(jì)算能力是等價(jià)的，兩種模型定義的“可計(jì)算性”實(shí)際上殊途同歸。他將這個(gè)結(jié)果作為附錄補(bǔ)充到了他的論文。
對(duì)于圖靈來說，這既是個(gè)壞消息，也是個(gè)好消息。壞消息是，他的結(jié)果與丘奇的重復(fù)了，對(duì)于發(fā)表文章來說，這不是什么好事情。好消息是，他的結(jié)果與丘奇的重復(fù)了，但他對(duì)可計(jì)算性的定義與丘奇的截然不同，而且兩種看似毫無關(guān)系的定義，在實(shí)質(zhì)上是相同的，這說明，他們對(duì)可計(jì)算性的定義，這最初的一步踏出的方向是正確的。一個(gè)人提出的定義很可能忽視某個(gè)方面，但現(xiàn)在兩個(gè)截然不同的定義引向相同的結(jié)果，在交叉印證下，幾無出錯(cuò)之虞。
可以說，圖靈的工作面世之日，正是可計(jì)算性理論呱呱墜地之時(shí)。
也難怪紐曼教授一開始不相信圖靈的工作。僅僅二十出頭，剛剛踏入科學(xué)界的年輕人，就解決了如此重要的問題，而且為一個(gè)全新的領(lǐng)域立下了奠基石，這種人，即使在劍橋這個(gè)英國(guó)頂尖學(xué)府，也可謂難得一見。倒不如說，一開始不相信，這才是正常的反應(yīng)。
但即便不相信，數(shù)學(xué)證明就是證明。即使紐曼教授并不專精于數(shù)理邏輯，還是能看出圖靈論文的過人之處。他決定為圖靈爭(zhēng)取發(fā)表的機(jī)會(huì)。
這并非易事。因?yàn)閺慕Y(jié)論上說，圖靈重復(fù)了丘奇的結(jié)果，所以最初聯(lián)系的幾個(gè)期刊的編輯都婉拒了紐曼的要求：他們只看到了論文的結(jié)論，沒看到論文的精髓。最后，紐曼找到了當(dāng)時(shí)倫敦皇家學(xué)會(huì)學(xué)報(bào)的編輯，經(jīng)過三催四勸，終于說服編輯發(fā)表圖靈的文章。
《論可計(jì)算數(shù)，及其在可判定性問題上的應(yīng)用》，圖靈的這篇文章，后來被認(rèn)為是倫敦皇家學(xué)會(huì)學(xué)報(bào)發(fā)表過的最重要的文章之一。
乘著遠(yuǎn)洋貨輪，圖靈的論文很快傳到了大洋彼岸，在普林斯頓掀起了一陣旋風(fēng)。
在普林斯頓高等研究院的哥德爾，與丘奇有過不少碰面的機(jī)會(huì)。他讀過丘奇的論文，大概也聽過丘奇本人介紹他的λ演算。但哥德爾對(duì)λ演算一直頗有微詞。實(shí)際上，作為一種計(jì)算模型，λ演算從未得到他的認(rèn)可。它與人們?nèi)粘＝佑|到的“計(jì)算”毫無相似之處，更像是符號(hào)的堆砌和推演。雖然其中的計(jì)算的確可以機(jī)械性地完成，但要證明這一點(diǎn)絕非易事。事實(shí)上，這是一個(gè)遠(yuǎn)非顯然的定理，證明也相當(dāng)復(fù)雜?？偠灾搜菟悴⒉幌駲C(jī)械的計(jì)算，更像智慧的推理。
實(shí)際上，哥德爾自己也有一套“機(jī)械計(jì)算”的模型，那正是他在證明哥德爾不完備性定理時(shí)發(fā)展出來的遞歸函數(shù)體系。這套體系將“機(jī)械計(jì)算”定義為遞歸函數(shù)能計(jì)算的內(nèi)容，而遞歸函數(shù)，顧名思義，就是可以用某些遞歸方式定義的整數(shù)函數(shù)。但哥德爾對(duì)他自己的模型同樣不滿意，原因同樣是他的模型似乎需要太多的聰明才智，不像一臺(tái)機(jī)器。
但圖靈的論文瞬間就令哥德爾為之折服。
任何人，只要看一眼圖靈機(jī)的定義，都會(huì)認(rèn)同圖靈機(jī)的計(jì)算完全是機(jī)械演算，完全可以造出一臺(tái)可以運(yùn)作的實(shí)際的圖靈機(jī)。而更重要的是，圖靈機(jī)抓住了“機(jī)械計(jì)算”的神韻。
機(jī)械計(jì)算是什么？是機(jī)器可以做出的計(jì)算。但機(jī)器可以千奇百怪，要用三言兩語抓住本質(zhì)，似乎不太可能。那么，何不反其道而行之？與其想像這些機(jī)器共有的特性，不如尋找它們共有的限制。
這正是圖靈在論文中的做法。他總結(jié)了以下幾個(gè)機(jī)器計(jì)算的限制：
第一：一臺(tái)機(jī)器只有有限個(gè)可以分辨的狀態(tài)；一臺(tái)機(jī)器能分辨的表示數(shù)據(jù)的符號(hào)只有有限種。
開關(guān)或開或合，電路或通或斷，中間的變化是跳躍式的。即使是連續(xù)的電信號(hào)，由于不可避免的熱噪聲影響，通過測(cè)量能分辨出的狀態(tài)同樣只有有限個(gè)。雖然現(xiàn)代的計(jì)算機(jī)看似有無限可能，但這只是幻覺。CPU和內(nèi)存中的電路，數(shù)量雖然龐大無比，但總歸是有限的，它們的通斷形成的不同狀態(tài)亦是如此。同理，雖然符號(hào)、信號(hào)在細(xì)節(jié)上可以有無數(shù)種變化，但由于精度等問題，即使是人，也無法事無巨細(xì)將所有細(xì)節(jié)一一分辨出來，更何況機(jī)器。
第二：機(jī)器的每一步操作需要的時(shí)間有一個(gè)下限，而每次操作最多只能讀入與改寫外部有限個(gè)符號(hào)。在某次操作讀寫某處的符號(hào)后，下一步機(jī)器讀寫的符號(hào)與之前符號(hào)的距離應(yīng)該是有界的。
由于物理的限制，不存在速度無限的物體。無論任何機(jī)器，都不能在有限的時(shí)間內(nèi)作出無限次操作，當(dāng)然也不可能有無限次讀入與改寫。同樣，讀寫頭移動(dòng)的速度是有限的，所以兩次操作讀寫符號(hào)的距離當(dāng)然也有限制。
第三：在某步操作中，機(jī)器的行動(dòng)完全取決于它當(dāng)時(shí)的內(nèi)部狀態(tài)以及讀取到的符號(hào)。
機(jī)器就是機(jī)器，它應(yīng)該做的，就是按照預(yù)先規(guī)劃的圖紙一步一步執(zhí)行。沒有異想天開，沒有靈光一現(xiàn)，只有照章辦事，只有步步為營(yíng)。
這幾個(gè)限制看起來相當(dāng)合理，甚至顯得理所當(dāng)然。但就從如此平平無奇的限制出發(fā)，圖靈用縝密的邏輯說明了，一臺(tái)服從這些限制的機(jī)器能計(jì)算的問題，必定可以用一臺(tái)特定的圖靈機(jī)解決。也就是說，任何一臺(tái)服從這些限制的機(jī)器，無論設(shè)計(jì)如何精巧，構(gòu)成如何復(fù)雜，它的計(jì)算能力都不可能超越圖靈機(jī)，無一例外。
我們甚至可以說，圖靈機(jī)的設(shè)計(jì)本身，正是這些限制的一種體現(xiàn)。圖靈很可能一開始就意識(shí)到了這些限制，再由此出發(fā)，去定義他的圖靈機(jī)。哥德爾之所以對(duì)圖靈機(jī)擊節(jié)嘆賞，大概也正因蘊(yùn)含在它定義中的，圖靈對(duì)“機(jī)械計(jì)算”的深刻洞察。相比之下，雖然與之等價(jià)的λ演算也尚算精致，但對(duì)于“機(jī)械計(jì)算”只得其形未得其神，顯然遜色不少。
現(xiàn)在，希爾伯特在他的問題中那模糊的“機(jī)械計(jì)算”，終于有了一個(gè)精確的定義：機(jī)械計(jì)算，就是圖靈機(jī)能做的計(jì)算。這又被稱為圖靈-丘奇論題，正是可計(jì)算性理論的奠基石。
除了λ演算與遞歸函數(shù)以外，還有許多計(jì)算系統(tǒng)與圖靈機(jī)等價(jià)。波斯特對(duì)應(yīng)問題，計(jì)數(shù)器機(jī)，馬爾可夫算法，甚至元胞自動(dòng)機(jī)，這些計(jì)算模型都與圖靈機(jī)等價(jià)。但以我們的后見之明來看，圖靈機(jī)仍然是機(jī)械計(jì)算最自然最有用的模型之一。
也正因這篇論文，圖靈得到了到普林斯頓讀博深造的機(jī)會(huì)，在丘奇的指導(dǎo)下，得以繼續(xù)探索可計(jì)算性的無限可能。在大洋彼岸等待圖靈的，又是可計(jì)算性理論的一篇新章。
相關(guān)文章聯(lián)系客服
