一、主要問題
照規矩算題這件事有一個特點: 會算的人不必懂。
一個人拿到一道加法題, 照著竪式往下寫, 不必知道這些數代表什麼, 也能算對。規矩在紙上, 人只負責執行。
十九世紀末, 數學家開始想一件更大的事: 數學裡的問題, 是不是全都能這樣辦。隨便給一個一階邏輯公式, 有沒有一套死規矩, 照著走有限多步, 就能判出它是不是在任何解釋下都成立。
要的不是讓聰明人去想, 是讓一個不懂的人照著做也能做出來。
這樣一套規矩, 當時的說法叫程序。它存不存在, 是1928年一本教科書指認的數理邏輯主要問題。
它不存在。這件事在1936年被證明瞭。而證明它的人為了把話說死, 必須先把程序這樣東西整個界定一遍; 為了界定它, 他造了一臺機器。
那臺機器, 後來被當作計算機的模型。
1928年, 柏林一家出版社印出一本教科書, 《理論邏輯綱要》, 作者是大衛·希爾伯特與威廉·阿克曼。希爾伯特是哥廷根的數學教授, 當時數學界分量最重的人物之一; 阿克曼是他的學生。
書裡寫著一個問題。給定一個邏輯表達式, 要求有一套程序, 能夠通過有限多次操作, 判出它是不是無論怎麼解釋都成立, 或者至少在某一種解釋下能成立。
同一頁上還有一句評價: 判定問題必須被稱為數理邏輯的主要問題。
這句話不是推薦, 是指認。用的是必須。
它沒有說這個問題很有趣, 沒有說它值得研究, 它說的是主要。一門學問把自己的核心指定在一個地方, 這個地方就成了此後所有工作的度量。誰做出了它, 誰就做成了這門學問要做的事; 而它一旦被證明做不成, 這門學問也得跟著改一次自己的樣子。1928年寫下這句話的時候, 書裡沒有給後一種留位置。這本書是教科書, 教科書裡寫下的東西是給學生學的, 不是給學生懷疑的。一個問題被寫進教科書, 就等於宣佈它是一道正經的題; 而正經的題, 默認是有答案的。
這個要求早有前身。1900年八月在巴黎, 希爾伯特列出的問題清單裡, 第十條要求對任意給定的一類方程給出一套程序, 用有限多次操作判定它有沒有整數解。那一條比1928年這一條窄, 判定的是一類特定的算術方程; 但用詞是同一批用詞: 程序, 有限多次操作, 判定。二十八年裡, 要求的範圍在擴, 要求的形狀沒有變。同一次演說的總論裡還有另一句, 說明確提出的數學問題應當得到確定的解決, 或者得到不可能解決的證明。後半句在當時是一句退路, 三十六年後成了正門。
1917年在蘇黎世, 他把可判定性, 以及通過有限多次操作的可判定性, 列為需要研究的對象。1922年, 海因里希·貝曼的一篇論文題目裡直接用上了判定問題這個詞, 文章裡說, 真假的判定應當退化成按照既定指令進行的機械計算。這句話已經把要的東西說出來了: 一套指令, 照著走, 不用想。1922年到1923年的冬季學期, 希爾伯特與保羅·伯奈斯在哥廷根開過一門數學的邏輯基礎。
從1900年到1928年, 這個要求越寫越清楚。而它裡面有一樣東西始終沒有被寫清楚。
程序是什麼。
有限多次操作, 這五個字裡的操作指的是什麼樣的動作。一套按既定指令進行的機械計算, 機械兩個字管到哪裡。這些沒有人定義過, 因為在1928年, 它們看上去不需要定義: 一個數學家看見一套算法, 認得出來那是不是一套算法。認得出來, 於是不必定義。
要證明一件事做不到, 這一步就繞不過去了: 得先把那件事的全部可能一樣不漏地圈起來。圈不起來, 就沒法說不存在, 只能說還沒找到。找不著, 不構成證明; 只有把可能的全部形狀描出來, 才談得上說裡面沒有。這是圖靈那份稿子的形狀: 先造一個盡可能大的籠子, 再證明有東西在籠子外面。籠子造得越大, 那件在外面的東西就越確鑿。第九節專門交代這只籠子為什麼圈得住: 一條一條堵住可能被人說漏的地方, 而每堵一處, 他伸手去拿的都是那個算題的人身上的一樣東西。
整整二十八年, 這一邊要求給出一套程序, 那一邊沒有人定義過程序是什麼樣的東西。要求已經立起來了, 被要求的那樣東西卻還沒有形狀。構在這裡向外伸手, 抓的是一個自己還叫不上名字的東西。而後來發生的事情之所以能發生, 正是因為有人先回過頭去, 把這個沒有名字的東西造了出來。
二、兩個會場
1930年九月, 哥尼斯堡。這一週裡發生了兩件事, 後來常被說成同一件。
其中一件, 後來被認為改寫了整門學問, 當時在場的人沒有一個當場說話。要過一年多, 那篇論文印出來, 事情才慢慢被人看清。一件事在發生的當下往往沒有形狀, 形狀是後來印在紙上的。
第一件是九月五日到七日的第二屆精密科學認識論會議, 由一個經驗哲學的團體主辦。當時關於數學的地基該怎麼打, 有幾派互不相讓的看法。五日的場次就是讓各派各講一小時, 約翰·馮·諾伊曼講的是希爾伯特那一派。六日是另一批講演, 一位二十四歲的維也納人庫爾特·哥德爾有一個二十分鐘的短講, 講的是他剛做完的一項工作。
七日星期天, 會議安排了一場數學基礎的討論, 由漢斯·哈恩主持, 馮·諾伊曼和哥德爾都發了言。在這場討論快結束的時候, 哥德爾宣佈了一個還沒有正式發表的結果。
第二件事是九月八日希爾伯特的演說, 題目是《自然認識與邏輯》。這一場不屬於上面那個會議, 它屬於隨後在同一座城市舉行的德國自然科學家與醫生大會。另有一個約四分鐘的廣播版本, 錄音留存了下來, 末尾是那句: 「我們必須知道。我們將會知道。」
這句話是對著數學這門學問說的, 說的是不承認有原則上不可知的東西。它針對的是當時另一種流行的說法: 有些事情人永遠弄不明白, 到此為止。他反對的是那個到此為止。六年之後, 從他自己那門學問裡長出來的一件東西, 給出了一個此路不通的證明; 而那個證明的形狀, 與他反對的那種到此為止並不一樣: 它不是說人弄不明白, 它是說這件事本身不存在。這兩句常被混在一起, 而它們在這個系列裡的位置完全不同: 前一句是關於人的限度, 後一句是關於世界的形狀。
這兩件事挨著, 隔一天。後來的敘述常常把它們擺成一個場面: 宣告的話音剛落, 取消它的結果已經在隔壁說出來了。
那一週的記錄裡, 看不到這兩個人碰面。九月七日那場討論的與會與發言名單上沒有希爾伯特; 第二天的聽眾席上有沒有哥德爾, 也沒有一行字提到。兩個房間, 各開各的會, 沒有一條記錄說它們聽見了對方。
後來那個場面, 把一件複雜的事講成了一句話。而那一週紙上的樣子, 是幾十個人分在兩個會裡, 各講各的, 其中一個人在星期天下午快散場的時候說了一件事, 沒有人接話。
哥德爾1931年的論文發表在一份數學月刊上, 講的是一件相關但不同的事: 在他所研究的那類形式體系裡, 只要它能夠表達算術, 也滿足相應的一致性條件, 有些句子既證不出來, 也證不出它的反面。所謂體系, 指的就是這樣一套寫死了的東西。
它沒有解決那本教科書上的問題。判定問題要的是一套對任意一階邏輯公式都管用的通用程序, 而1931年那篇講的是某一類體系內部的句子。到1936年為止, 判定問題仍舊敞著。
三、1936年的三份稿子
1936年, 三份稿子先後落地, 來自三個人, 互不相同的路子。三個人都碰到了同一件事: 怎樣把按規矩計算說得精確。一個用函項與代換的演算, 一個用一條帶子和一張行為表, 一個用一串格子和一個照指令作業的人。相近的想法可以各自起頭, 但它們是不是同一個東西, 還得另花力氣去證。證完之後, 幾條路看上去就像本來就是一條。
三月, 一份新創刊的符號邏輯雜誌第一期上, 普林斯頓的阿隆佐·丘奇印出一則兩頁的注記, 題目裡直接帶著判定問題。四月, 他在一份美國數學雜誌上印出十九頁的長文, 《初等數論中的一個不可解問題》。
五月二十八日, 倫敦數學會收到一份稿子, 作者是劍橋國王學院的一名研究員, 阿蘭·圖靈, 二十三歲。文章題為《論可計算數, 及其在判定問題上的一個應用》。十一月十二日宣讀, 印出來是三十六頁。
十月七日, 那份符號邏輯雜誌收到第三份稿子, 作者是美國數學家埃米爾·波斯特, 題為《有限組合過程·表述一》。三頁, 是這三份東西裡最短的一份。它印在一份創刊不久的雜誌上, 而那份雜誌的編輯之一, 正是三月和四月兩篇的作者。同一個人的名字在這一年裡出現了三次: 一次作為作者, 一次作為被追趕的人, 一次作為收稿的編輯。第二年他還會再出現一次, 作為寫書評的人和作為導師。而給這臺機器起名字的, 也是他。
圖靈在文章開頭就承認丘奇近來的工作已經給出了不可解的結果, 並在附錄裡證明自己那套可計算與丘奇那套可定義性彼此等價。
這個附錄說明, 這篇文章在投出去之後被改過: 一個人的結論已經先被別人得到了, 於是他必須證明自己那條路與別人那條路通到同一處。這段證明不是原來的計劃, 是被時序逼出來的。
同一件事他在第二年另有一句話。1937年他在一篇比較兩種表述的文章開頭寫道, 自己那一套或許更有說服力。兩套東西在數學上等價, 而在說服力上不等價; 差別不在結論, 在理由的形狀。
波斯特那三頁文章印出來時, 頁腳有一條編輯注, 請讀者比較圖靈那篇即將刊出的論文, 並且專門聲明: 波斯特這篇雖然日期在後, 寫作完全獨立。
到這裡為止, 1936年的事實是: 丘奇與圖靈分別證明瞭判定問題無解; 波斯特獨立提出了另一種計算模型, 預期它與哥德爾和丘奇所說的遞歸等價。他那三頁不是同一結論的第三份證明。
兩種正式定義彼此等價, 後來被當成一條重要證據。但在1936年, 對圖靈而言, 得先花力氣證出他的辦法與丘奇的辦法算的是同一類東西, 才能指出兩條路在哪裡會合。
1937年, 圖靈印出一份三頁的更正, 寫明是伯奈斯指出了原文中的錯誤。這篇後來被反覆稱作奠基之作的文章, 出來一年之內就有人在裡面挑出了錯; 改了, 機器和結論都還在。
四、那個正在算題的人
圖靈那篇文章的第九節, 開頭承認了一件事: 到那裡為止, 他還沒有證明自己形式化的可計算這個詞, 裝得下人們通常會叫作可計算的全部東西。
他給出三類理由。第一類是直接訴諸直覺, 第二類是證明不同的定義彼此等價, 第三類是給出大量的實例。
而這一類理由所分析的對象, 是一個正在用紙和符號算題的人。
1936年英文裡, 計算者這個詞指人。它是一種職業, 也是一個可以寫在履歷上的頭銜。一批人坐在桌前, 按照給定的規則一步步往下算, 算出表來。天文的表, 航海的表, 保險的表, 都是這樣算出來的。這種人當時到處都是, 大多是被雇來做重複勞動的, 一間屋子裡坐一排, 各人負責一段。這個詞要到幾十年後才被讓給機器。讓給之後, 原來那批人換了別的名字, 或者沒有名字。一個職業的名稱被搬到機器身上, 通常意味著那件活已經不再算作一件活。圖靈這一節裡用來指稱這個執行計算者的代詞是他。
他寫下的一句是: 這個人在任何一刻的行為, 由他此刻正在觀察的那些符號所決定。緊接著他把這個人當時的心靈狀態也加了進去, 作為另一個決定因素。
所以這個模型從一開始就有兩樣東西: 看得見的符號, 和看不見的狀態。整節往下走的方向, 就是把後一樣也弄成看得見的。做不到就換掉。這是第九節第三個論證用的辦法, 也是這一整篇文章的辦法。
然後他一條一條往下收。收的辦法很一致: 每一條都從人做得到什麼出發, 而不是從數學上什麼方便出發。
紙通常是二維的。他把它改寫成一條分成格子的帶。理由不是說人實際上都用紙帶, 而是說二維這件事對計算不是本質的, 二維的佈局可以繞開。
可用的符號種類必須有限。他給的理由不是數學上的, 是經驗上的: 如果把很長的一串字當作一個復合符號, 長度一大, 人就不能一眼認出來。他舉的例子是兩串極長的九, 人沒法一眼判斷這兩串是不是一樣。
這個理由是經驗的, 不是形式的。要給一門最講究嚴格的學問定下一個基本概念, 他拿出來的證據是人眼睛不夠用。整套模型的邊界, 在這一處是照著人的能力量出來的: 不是照著物理, 不是照著邏輯, 是照著一個人能不能一眼看清。後來, 它常被當成了機器自己的性質。
一個時刻能觀察到的格子數有一個上界, 他記作一個字母。要看更多, 只能連續地看下去。
需要考慮的心靈狀態數目也必須有限。他給的理由是: 如果允許無限多個狀態, 就會有些狀態彼此靠得任意近而被混淆; 而複雜的狀態可以有一部分轉移出去, 變成寫在帶上的更多符號。
這一句裡有一個動作: 轉移出去。心裡的東西太多裝不下, 就寫到紙上去; 而寫到紙上之後, 它就不在心裡了。心裡剩下的越少, 需要假定的就越少; 需要假定的越少, 論證就越站得住。所以整節的方向是一直往外倒: 把裡面的東西倒到紙上, 直到裡面空了為止。
眼睛下一次落到哪裡, 也有限制。存在一個固定的距離, 新觀察到的格子不能離先前剛看過的格子太遠。他討論過一種反例: 遠處有編號的格子似乎可以一眼認出來; 他的回答是, 編號一長, 仍舊得逐個字符去核。
把這些假定合起來, 他造了一臺機器, 去復現這個人的計算工作。這個人所考慮的每一個心靈狀態, 對應機器的一個內部構型; 機器掃描相應數目的格子, 並在有界的距離內改變觀察的位置。
機器可以復現的, 是這裡被分析的這一段符號計算過程。他復現的是這樣一份活: 一個照規矩算題的人所做的事。它很具體, 也很枯燥, 此前就是有人拿工錢在做的。
同一年秋天, 另一個人在三頁紙上寫的是同一個東西的另一種樣子。波斯特設想的符號空間是一串向兩頭無限延伸的格子, 每格只有空白與帶記號兩種狀態。在那裡作業的, 他叫作解題者, 或者工人。這個人在某一格上作業, 服從一組固定不可改動的指令; 基本動作是查看當前格有沒有記號, 擦掉, 做記號, 向右一格, 向左一格。
兩份稿子隔著一個大西洋, 用的詞不一樣, 出發的對象是同一樣東西: 一個人, 一疊紙, 一套不許改的規矩。
兩個人各自去想計算是什麼, 各自想到的第一樣東西, 都是一個正在幹活的人。不是一臺鐘, 不是一架織機, 不是一串電路。他們要做的模型是關於計算的, 而當時世上最像計算的東西, 就是一個照規矩算題的人。
五、紙上的字條
第九節還有第三種處理。在這個論證裡, 圖靈給心靈狀態找了一個紙上的替身。第一個論證裡, 有一個別人看不見, 也沒法核對的東西; 而整篇文章要做的, 是把一件事說死。
他設想這個計算者可以停下來, 離開, 把事情忘掉, 然後靠留在紙上的一張指示條回來接著做。這張字條連同帶上已有的符號, 構成了對心靈狀態的一個更明確的物理對應物。
這裡的處置方式是: 他沒有說心靈狀態不存在, 沒有說它不重要, 也沒有去研究它是什麼。他找了一樣東西, 讓論證在沒有它的情況下照樣走得通。原來的位置上擺著一個別人查不了的東西, 現在那個位置上擺著一張紙。紙可以傳給別人看, 可以被抄, 可以被核對, 可以被人拿去接著做。一件東西一旦能被別人接著做, 它就不再需要原來那個人。這一句在1936年是論證的一步, 在此後一百年裡是很多人的處境。而在這一節裡, 它還只是一個論證上的方便, 用來去掉一個查不了的假定。
他甚至讓這個人每次坐下來只做一步, 做完就寫下一張繼續工作的指示。這樣一來, 計算走到某個階段的全部狀態, 就完全記錄在那張字條和帶上的符號裡。
這個人可以換成另一個人。他坐下來, 讀那張字條, 做一步, 寫下新的字條, 走人。誰來做這一步不影響結果, 因為要做什麼全寫在紙上。做這件事的人在這一刻變成了可替換的。第一個論證裡那個人還帶著自己的心靈狀態; 第三個論證裡, 他連同他的心靈狀態一起被移到了紙面上, 而移過去之後, 那個位置上是誰已經無所謂了。
這個手法此後一直在用。凡是遇到一樣夠不著又繞不開的東西, 就找一個夠得著的替身放進去, 讓論證接著走。替身好不好用, 看論證走不走得通; 而被替下去的那個東西究竟怎麼樣, 這個問題從此可以不回答。
他做的是: 為一份具體的紙筆勞動造了一個模型。別人後來說的是: 這個模型就是心靈的模型。這兩句之間隔著一整段路, 而那段路在1936年這三十六頁裡一步也沒有走。
從這裡看得出這個系列後面要反覆遇到的一件事: 一個替身被放進論證之後, 它會留在那裡。論證走通了, 替身就成了正主; 而被替下去的那樣東西, 沒有被證偽, 也沒有被承認, 只是慢慢不再被提起。
六、一臺能當所有機器的機器
第六節的標題是通用計算機。
這一節開頭, 圖靈寫道: 可以設計出一臺單獨的機器。往下他規定, 把另一臺機器的標準描述輸進這一臺, 它就算出與那一臺相同的序列。第七節給出了這臺機器完整的行為表。
這臺機器的做法, 是把另一臺機器的描述當成數據吃進去。描述與被描述的東西在這裡落到了同一條帶上: 一臺機器的規格, 變成了另一臺機器要處理的符號。這一步在1936年只是一個證明上的方便, 後來成了一個行業的前提。
這樣一臺機器的位置很特別。它不是眾多機器裡最強的一臺, 它是能當任何一臺的那一臺。凡是這一類裡做得出來的事, 它都做得出來。構在這裡第一次做到了在自己那一類裡合攏: 裡面再沒有它夠不著的東西。
此前各處的構都是往外長的, 長一寸, 外面就少一寸, 而外面永遠還有。這一臺不一樣: 它一次就把自己那一類佔滿了, 不必再往外長。要它做別的事, 不必改造它, 只要換一段送進去的符號。提花機早就能換卡片, 那架木頭鋼琴也能換前提; 但它們可以換的東西, 各自在自己的規矩裡。這一臺把機器和它要做的事分開了。分開之後, 機器這個詞的意思也跟著變了: 從一件為某事而造的東西, 變成一件等著被指派的東西。而指派的人還在外面。指派什麼, 由誰定, 這兩件事沒有被這臺機器接管, 也沒有被這篇文章討論。此後每一次有人把新的一塊活挪進機器, 這兩件都還在原處。
而就在同一篇文章裡, 第八節給出了一個否定結論: 不存在一般的程序, 能夠對任意輸入的機器描述, 總是判定那臺機器屬不屬於他定義的某一類。第十一節把這個不可判定性轉移到1928年那本教科書所用的那套邏輯記號上, 最後寫出結論: 八年前被指認為數理邏輯主要問題的那個問題, 無解。
兩件事在同一篇文章裡。構在自己的類裡合攏了, 同時被證明有外面。
而且這兩件事是同一套東西推出來的。正因為任何一臺機器都可以被寫成一串符號送進那一臺, 才能拿這串符號去做那個構造; 正因為它無所不能地模仿同類, 才能問出那個它答不了的問題。合攏與有外面, 在這裡不是兩個結果, 是一個結果的兩面。
而且這個外面不是暫時的, 不是等技術進步了就沒有的, 不是造得更大更快就能進去的。它是被證出來的。
此前兩篇裡的界都是人劃的: 一個人看著一臺機器, 說它到這裡為止。這一次劃界的不是人的判斷, 是機器自己那套規矩推出來的一條限。誰也不能靠改主意把它挪走。此後每一次有人說機器做不到某件事, 都可以問一句: 說的是這一種做不到, 還是另一種。這是這個系列裡第一次, 餘項不是由人指著說這裡還剩著什麼, 而是從構自己的規矩裡推出來的。
用後來常見的停機問題打個比方, 這類辦法的形狀是這樣: 假定那套判定的程序存在, 就可以拿它去造出一臺機器, 這臺機器專門跟自己過不去, 凡是判定結果說它會做的事, 它偏不做。於是那套程序對這臺機器給不出一個自洽的答案, 而它本該對任何機器都給得出。假定因此站不住。這類論證叫對角線論證。圖靈原文第八節所問的, 是機器能否持續輸出, 以及能不能判出它是否會印出指定的記號。
這臺機器在文中被用來走到這一步。
為了把一件事說準, 得先把什麼叫做得到說清楚; 而什麼叫做得到, 在這篇文章裡有了一臺機器的形狀。後來那套計算的模型, 在這裡是一份否定結論的一環。
那臺機器是被當作證據用的。要證明沒有任何程序能做某件事, 就得先說清楚程序能是什麼樣子; 說清楚了, 才能把所有可能的程序一網打盡, 再指著其中做不到的那件事。機器是那張網。造網的人當時要抓的不是機器, 是程序; 而網織好之後, 它自己成了留下來的那樣東西。
七、名字是後來給的
那三十六頁裡, 智能這個詞一次也沒有出現過。
心靈這個詞出現過, 幾乎都是第九節裡反覆出現的那個人的心靈狀態; 那不是關於機器有心靈的主張, 那是計算者的一個狀態變量, 而且隨即被第三個論證裡的紙條頂替掉了。後來引這篇文章, 常常是反過來讀的: 一個關於人的變量, 被讀成了一句關於機器的許諾。
思考這個詞也出現過, 用在我認為, 可能有人會認為這樣的普通說法裡。這篇文章沒有提出機器能否思考這個問句。
此後八十年裡, 這篇文章常被當作那個問句的起點。它回答的, 是另一個問句: 那套程序存不存在。這個問句從1900年問到1936年, 三十六年。問了三十六年, 答案是沒有。而給出這個答案要付的代價, 是先把計算這件事整個定義一遍。定義完之後, 那個否定的答案只佔了幾頁, 而那份定義留了下來。
還有一個詞也沒有: 圖靈機。他自己用的詞是計算機器, 自動機器, 選擇機器, 通用計算機。
這個稱呼出自1937年三月丘奇為這篇文章寫的書評。命名它的, 是那位比它早兩個月拿到同一個結論的同行, 在它印出來的第二年, 在評價它的時候。丘奇在同一篇書評裡作了一個直接的比較: 圖靈那套可計算, 使它與通常意義上的有效性之間的等同立刻顯得明白。說這句話的, 是那個先做出結果的人, 是那份雜誌的創刊編輯之一, 也是圖靈接下來兩年的導師。
其餘的名字來得更晚。丘奇論題這個稱呼, 是邏輯學家斯蒂芬·克萊尼1952年在一本元數學教科書裡開始這樣叫的; 丘奇和圖靈合名的那個稱呼, 出自克萊尼1967年的一本書。1936年那三個人自己, 誰也沒有用過這些稱呼。三十一年之後, 才有一個稱呼把兩個名字並在一起; 而那時候兩位當事人裡已經有一位不在了。名字是別人給的, 給的時候人不在場; 這在這個系列裡已經是第三次。
關於名字, 波斯特在他那三頁的最後一頁上寫下過一段警告。
他把丘奇那種把有效可計算與某個形式類等同起來的做法, 稱作一個需要繼續檢驗的工作假說, 並且明確反對把這種等同藏在定義這個詞底下。那句話的結尾是: 「會使我們看不見它需要不斷檢驗」。
這句話寫在1936年, 一個人在事情剛做成的時候就指出: 把它叫作定義, 就等於宣佈它不必再被檢查。
他要守的不是一個技術上的分寸。定義是約定, 約定不必對世界負責; 假說是主張, 主張要一直等著被推翻。同一個命題掛在哪個名下, 決定了此後還要不要有人去看它。他要守的是這個: 別讓一個名字替大家把事情結掉。
而它後來的名字, 正是定義與論題這兩個詞輪流坐莊。波斯特寫下那段話的時候, 這兩個名字都還沒有出現。
八、哥德爾挑了哪一個
圖靈1936年九月底到普林斯頓, 此後兩年在那裡讀研究生, 導師是丘奇。1938年他在那裡取得博士學位。1938年四月, 馮·諾伊曼提議他留下來做自己的助手; 他謝絕了, 回了劍橋。
圖靈在普林斯頓的那兩年, 哥德爾不在那裡。兩人之間, 沒有留下一封信, 一條會議筆記, 一篇合作論文。後來的敘述裡, 這兩個名字常被擺在一起, 因為擺在一起實在太順手了。
在圖靈之前, 他對丘奇那一套並不滿意。丘奇1935年十一月的一封信裡說, 哥德爾認為把可定義性當作有效可計算的定義, 這個提議徹底不能令人滿意; 他當時更傾向於把有效可計算先作公理化處理。
1946年, 在普林斯頓兩百週年的一次數學會議上, 哥德爾發言說, 這套東西的重大之處, 在於第一次給出了一個不依賴於所選記號體系的絕對的定義。他強調的是這個概念的絕對性。絕對的意思是: 換一套形式體系, 這個概念不跟著變。他用的詞是第一次。1936年之前的每一次嘗試, 在他看來都還沒有到這個份上, 包括他自己1934年在普林斯頓講過的那一輪課。此前的每一個定義都掛在某一套記號上, 換一套就得重來一遍。
1963年, 他為自己1931年那篇論文加了一條注, 說尤其由於圖靈的工作, 現在能夠對形式系統這個一般概念給出一個精確而無可置疑地充分的定義。注裡接著說明, 他所謂真正意義上的形式系統, 特徵在於其中的推理原則上能夠完全由機械裝置來替代。
這條注寫在1963年, 加在一篇1931年的文章後面。三十二年之後, 他回頭給那篇文章補上了一個當時缺的東西: 形式系統是什麼。而補上這個的, 是一個1936年為了另一件事造出來的模型。
1964年, 他為1934年的一份講義寫後記, 說圖靈的工作給出了對機械程序這個概念的分析。同一份後記裡, 他把另一個問題留著沒有關。他在那裡問的是: 是不是存在有限的, 非機械的程序。
給這套東西蓋上章的那個人, 在蓋章的同一份文件裡, 明說自己沒有把它擴成對人的全部心智過程的界定。他認可的是一樣具體的東西: 機械程序這個概念被分析清楚了。至於機械程序之外還有沒有別的, 他把問題寫在那裡, 沒有回答。
晚年的談話裡, 他說得更滿一些: 在圖靈之前, 人們沒有把機械程序這個清晰的概念看清楚, 是圖靈帶來了正確的看法; 又說以圖靈機可執行來給出的那個界定是正確而唯一的。
餘項在這裡, 是由給這套東西蓋章的人親手留著的。
他認下了那個模型, 認得很重, 用了無可置疑地充分這樣的詞。就在同一處, 他把那個更大的問題另起一行寫著, 沒有往那邊推。
1947年, 哲學家路德維希·維特根斯坦在一冊手稿裡寫下一句話: 圖靈的那些機器。這些機器就是那些在計算的人。
緊接著的一句轉而說, 圖靈講的東西也可以用遊戲的形式表達出來; 再往下他寫出了自己的一個對角論證的變式, 並討論規則在某些位置變成無意義指令的情形。這句常被引來說人與機器的話, 寫下它的人當時在算一道對角線式的題。
那篇文章印出來以後的頭三年裡, 叫得出名字的讀者是這幾位。紐曼在投稿前就知道並討論過。丘奇寫了書評。伯奈斯讀到了能挑出錯來的程度。1937年二月, 圖靈還要人把一份抽印本寄給維特根斯坦。
名單就這麼長: 一位老師, 一位競爭者, 一位挑錯的人, 外加一份寄出去的抽印本。
1948年, 紐曼在一份皇家學會的會刊上發表《通用計算機器設計的一般原理》, 討論了圖靈那個通用機器的想法。那時候, 造一臺通用電子計算機已經是一道工程題了。而寫這篇文章的, 正是十二年前把那道題講給圖靈聽的那位。當年他在課上講的是一道邏輯題; 十二年後他寫的是一份工程說明。題目沒有變, 變的是它被拿來做什麼。同一樣東西, 十二年前是用來證明一件事做不到的, 十二年後是用來說明一臺機器該怎麼設計。一樣東西被證明不存在, 而為了證明它不存在所造的工具, 存在了下來, 並且被造成了實物。這件事在這個系列裡此後還會再發生, 形狀不同, 道理相同。
1930年九月那幾天的完整聽眾名單, 不存在。哥德爾那個星期天下午對著誰說的那句話, 誰聽見了, 誰沒聽見, 今天沒有人能列出來。而後來那個場面, 正是靠一份不存在的名單撐起來的。
一個二十三歲的人在1936年春天寫完了一份稿子, 為了證明一件事做不到。他從一個坐在桌前算題的人身上, 剝下了一臺機器。那臺機器後來被造了出來, 被叫作各種名字, 被用來問一個他在那篇文章裡一次也沒有提過的問題。
至於那個問題, 他自己十四年後才問。到那時候他手裡已經有一臺真的機器, 而剝下這臺機器的那個人, 那個坐在桌前照規矩算題的人, 已經不再被叫作計算者了。
機器還在造, 而界在哪裡, 每一代人重說一遍。