胡 嵩

(華中師范大學(xué) 馬克思主義學(xué)院，武漢 430070)

?

論圖靈的可計算思想

胡 嵩

(華中師范大學(xué) 馬克思主義學(xué)院，武漢 430070)

圖靈的可計算思想有著深刻的思想淵源，萊布尼茲、弗雷格和哥德爾對于人工語言研究的發(fā)展皆對圖靈的可計算思想有影響。圖靈在《論可計算數(shù)在判決性問題中的應(yīng)用》中提到圖靈機(jī)和通用計算機(jī)兩個抽象機(jī)器，并描述了兩種機(jī)器的基本結(jié)構(gòu)以及運行方式，其中，通用計算機(jī)是現(xiàn)代計算機(jī)的原型。圖靈的可計算思想從根本上影響了馮·諾依曼，并使得馮·諾依曼建造出人類第一臺計算機(jī)。圖靈對于現(xiàn)代計算機(jī)以及機(jī)器思維方面的發(fā)展所做出的貢獻(xiàn)是無法取代的。

可計算思想；圖靈機(jī)；通用計算機(jī)；現(xiàn)代計算機(jī)；機(jī)器思維

圖靈多數(shù)情況是因其論文被人提及，而他的名字與歷史上3個大型計算機(jī)項目是密切相關(guān)的。第一個是巨人(Colossus)。第二次世界大戰(zhàn)時，圖靈打破了恩尼格碼(Enigma，大西洋之戰(zhàn)的一個決定性因素)的神話，他在布萊切利公園設(shè)計出了“bombe(一種高速破譯德軍密碼的機(jī)器)”，從而破譯出恩尼格碼產(chǎn)生的大量軍事密碼。圖靈與他同事的工作使得二戰(zhàn)在歐洲戰(zhàn)場的時間縮短至少兩年[1]。二戰(zhàn)結(jié)束后，圖靈被英國的國家物理實驗室(the National Physical Laboratory)招募，他不僅設(shè)計了電子數(shù)字計算機(jī)(通用圖靈機(jī)的現(xiàn)實版本)，并對其發(fā)展做出了不可磨滅的貢獻(xiàn)，他的設(shè)計(the Automatic Computing Engine的設(shè)計)相比于其他學(xué)者構(gòu)建的更為先進(jìn)。在等待工程師建造ACE的同時，圖靈和他的團(tuán)隊開創(chuàng)了計算機(jī)程序科學(xué)的研究，為將要建造出的計算機(jī)寫了大量復(fù)雜的數(shù)學(xué)程序。隨后一年，西方國家的幾個團(tuán)隊開始著手在硬件方面做出一臺通用計算機(jī)。曼徹斯特大學(xué)的紐曼電子計算機(jī)實驗室率先做出一臺能夠運行的電子存儲計算機(jī)，這臺機(jī)器叫做“Manchester Baby”。隨后，圖靈在紐曼的力邀之下，參與了紐曼的計算機(jī)項目，并于1948年6月21日在該臺機(jī)器上運行了第一個程序。不久之后，圖靈為“Manchester Baby”設(shè)計出了輸入/輸出設(shè)備(I/O)和擴(kuò)大化的機(jī)器的程序系統(tǒng)，稱為“Manchester Mark Ⅰ”。

一、圖靈可計算思想的淵源

阿蘭·麥西森·圖靈生于1912年6月23日，卒于1954年6月7日。圖靈一生所致力的研究對于邏輯學(xué)、數(shù)學(xué)、生物學(xué)、哲學(xué)、密碼分析和隨后形成的計算機(jī)科學(xué)、認(rèn)知科學(xué)、人工智能和人工生命領(lǐng)域都有巨大貢獻(xiàn)。圖靈的可計算思想受萊布尼茲和弗雷格的影響，并在很大程度上受到哥德爾的啟發(fā)。

萊布尼茲是現(xiàn)代形式邏輯的構(gòu)設(shè)者和初步奠基者,他曾致力于把人的理性部分地還原為計算，并且用機(jī)器來執(zhí)行這些計算。萊布尼茲認(rèn)為他的宏偉計劃主要有3步：首先，創(chuàng)造一套能夠涵蓋所有人類知識的綱要或百科全書；其次，選擇其背后的關(guān)鍵基礎(chǔ)概念，為每個概念提供合適的符號，并證明為它們提供合適符號的可行性；最后，制定合適的演繹規(guī)則來操作這些被定義的符號，演繹規(guī)則即為萊布尼茲所說的“推理演算”。

弗雷格是萊布尼茲計劃的繼承者，他想要找到某種不用邏輯來發(fā)展邏輯的方法，他的方法是用精確的語法規(guī)則或句法規(guī)則，把概念文字發(fā)展成一種人工語言，而他的方法直接促使圖靈構(gòu)想出可計算思想。由于弗雷格試圖找到一個可以包含數(shù)學(xué)實踐中全部演繹推理的邏輯系統(tǒng)，并想以其邏輯為基礎(chǔ)把代數(shù)構(gòu)造出來，所以他引入了一些自己的特殊符號來表示邏輯關(guān)系。他發(fā)現(xiàn)那些連接命題的關(guān)系也可用于分析命題的結(jié)構(gòu)，于是把這些關(guān)系作為他的邏輯基礎(chǔ)，第一次用精確的句法構(gòu)造了形式語言。這一思想不僅成為后來現(xiàn)代邏輯的基礎(chǔ)，而且使得邏輯推理能夠轉(zhuǎn)化為機(jī)械演算的推理規(guī)則。與此同時，弗雷格的邏輯也給人們提出了一個需要研究的問題，即能否找到一種計算方法，能夠說明在他的邏輯中某一推理是否正確[2]，這個問題被稱為希爾伯特的“判定問題”，即：“對于一個一階邏輯的公式，如何找到一種方法，可以在定義明確的有限步驟內(nèi)判定這個公式是否是有效的?！盵2]

哥德爾對于這個問題的解決也給圖靈的可計算思想帶來了影響，當(dāng)他在思考希爾伯特的“判定問題”時，發(fā)現(xiàn)數(shù)學(xué)系統(tǒng)中始終存在一些無法被證明是否成立的命題。1931年，哥德爾發(fā)表了論文，提出了不完全性定理，證明了希爾伯特問題是不可判定的。在哥德爾的論文發(fā)表之后，人們已經(jīng)知道了希爾伯特所謂的算法是不存在的，但圖靈的一篇文章從另一個角度證明了不完全定理的正確性。

圖靈在1935年春得知了希爾伯特的“判定問題”之后，開始思考怎樣才能證明這樣的算法是不存在的，而后在1936年發(fā)表了他重要的論文《論可計算數(shù)在判決性問題中的應(yīng)用》。在這篇論文中他給出了一個新的數(shù)學(xué)推理分析，“判定問題”難以被一臺通用計算機(jī)所解決(即使有無限的時間和存儲)，圖靈描繪的這種抽象計算機(jī)(現(xiàn)在被稱為通用圖靈機(jī))被認(rèn)為是現(xiàn)代計算機(jī)的原型。

二、圖靈的可計算思想的主要觀點

《論可計算數(shù)在判決性問題中的應(yīng)用》[3]首次于1936年在《倫敦數(shù)學(xué)學(xué)會會刊》(ProceedingsoftheLondonMathematicalSociety)上出現(xiàn)。圖靈開創(chuàng)了計算機(jī)理論并推動了其發(fā)展，他在文中介紹了著名的通用計算機(jī)(在發(fā)表后就被美國邏輯學(xué)家丘奇稱為“圖靈機(jī)”[4])。這篇文章被看作是現(xiàn)代計算機(jī)科學(xué)的元論文。在20世紀(jì)30年代，它為電子存儲程序數(shù)字計算機(jī)的發(fā)展貢獻(xiàn)了極其重要的思想，而且它是現(xiàn)代計算機(jī)基本原理的來源。這個控制機(jī)器運作的思想是以存儲在計算機(jī)內(nèi)存中的編碼命令構(gòu)成的程序來實現(xiàn)的。

首先，圖靈描述了圖靈機(jī)的構(gòu)成。圖靈指出，一臺圖靈機(jī)是由一個掃描儀和一個能夠在掃描儀中來回移動的無限存儲紙帶所構(gòu)成。紙帶被分為若干個區(qū)域(格)，每個區(qū)域上是空白的或只有一個符號0或1(或是有限字母表上的符號)，掃描儀在一個時刻只能掃描紙帶上的一個區(qū)域(稱為被掃描區(qū)域)。掃描儀有擦除掃描區(qū)域的符號、在掃描區(qū)域?qū)懮戏枴⑹辜垘蜃蠡蛳蛴乙苿拥臋C(jī)制。除了這些操作之外，掃描儀還能夠改變圖靈所稱為的“m-格局(m-configuration)”，在現(xiàn)代圖靈機(jī)的術(shù)語中，通常用“狀態(tài)(state)”來代替“m-格局”。掃描儀中有能夠接受各種不同狀態(tài)的裝置，而且掃描儀能夠在必要的時候改變這個裝置的狀態(tài)，這個裝置的工作原理類似于一個簡單的存儲器。

這樣的操作(擦除、寫、移動和改變狀態(tài))是圖靈機(jī)的基本操作(原子操作)。操作的復(fù)雜性就在于將大量的基本操作連接起來。適用于商業(yè)的計算機(jī)是通過硬接線來完成最基本的操作，相比于圖靈機(jī)這類機(jī)器更為復(fù)雜。然而明顯的是，雖然圖靈機(jī)是很簡單的，但它可以計算任何商用計算機(jī)能夠計算的東西。事實上，因為圖靈機(jī)是抽象的機(jī)器，有無限的存儲，因此在現(xiàn)實中找不到一臺計算能力可以與之相匹配的計算機(jī)。

其次，圖靈描述了圖靈機(jī)的運行程序。圖靈所描述的計算機(jī)以一條空白紙帶開始工作，這個紙帶是無限長的，問題就在于啟動機(jī)器之后，掃描儀處于紙帶上的任何一個區(qū)域，從開始的地方向右運行，若給機(jī)器一個動力，掃描儀是否就會在紙帶上寫下所期望的數(shù)字?jǐn)?shù)列。為了做這項工作，這個機(jī)器需要處于某種“狀態(tài)”。當(dāng)機(jī)器開始工作時，它處于初始狀態(tài)，在一個掃描區(qū)域的操作完成之后，機(jī)器處于結(jié)束狀態(tài)，同時這個結(jié)束狀態(tài)是下一個掃描區(qū)域的初始狀態(tài)。機(jī)器要進(jìn)行的操作是由規(guī)則表所控制的，每一個指令規(guī)則表是由若干行格局(Configuration)和行為(Behaviour)所組成的，而格局可分為m-格局(m-configuration)和符號(symbol)，行為可分為操作(operations)和最終m-格局(final m-configuration)。這樣一行規(guī)則表由4個要素組成：(1)m-格局是機(jī)器的初始狀態(tài)；(2)符號是掃描儀在所停留的區(qū)域掃描到的符號；(3)操作是掃描儀在確定了掃描區(qū)域的初始狀態(tài)以及在掃描區(qū)域掃描到的符號之后，要進(jìn)行的操作(若有符號決定是否擦除，若無符號則決定是否在掃描區(qū)域打印符號，然后掃描儀向左向右或停止)；(4)最終m-格局是機(jī)器的結(jié)束狀態(tài)。一臺機(jī)器在某個指令規(guī)則表的指示下運行，也許會無止境地運行下去，同樣也可能在運行一段時間之后停止下來，這是取決于規(guī)則表的設(shè)計者是如何去設(shè)計這個規(guī)則表的。

在最后的分析中，一個計算機(jī)程序僅僅是一長串符號流或列，即為符號的組合體編碼命令。每一行的規(guī)則表命令可以再次改寫為qisjskMql形式的單個“單詞”，其中，qi表示的是初始狀態(tài)，位于規(guī)則表的最左側(cè)的一列，sj是在掃描區(qū)域被掃描的符號(空白被當(dāng)作是符號的一種)，sk是在掃描區(qū)域?qū)⒁粚懮系姆?，M表示掃描儀應(yīng)該移動的方向，向左向右或停止(有些時候，一行中可能沒有移動的指令，當(dāng)沒有移動的指令時則用“N”表示計算機(jī)停止)，ql是一個操作結(jié)束時的狀態(tài)。將每一行的規(guī)則表改寫成上述形式的“單詞”，連接起來寫成一行從而組成一長串的符號組合體編碼命令，在兩行規(guī)則表之間用分號分開[5]，在最后一行的規(guī)則表末尾用句號來表示一串符號組合體編碼命令的完結(jié)。這個字符串能夠轉(zhuǎn)換成一串由A C D L R和N這些字母所組成的字符(還有分號)，圖靈稱之為機(jī)器的標(biāo)準(zhǔn)描述，以這種方式進(jìn)行的變換過程能夠使每個單一的指令從標(biāo)準(zhǔn)描述中找回。將A C D幾個字母以不同的組合形式來代替原指令中的各種狀態(tài)和各種符號，L R N則代表了掃描儀完成一個掃描區(qū)域的擦寫程序之后應(yīng)該向左向右或是停止所指代的符號。這樣，一串符號組合體編碼命令便被轉(zhuǎn)換成為圖靈所說的標(biāo)準(zhǔn)描述，并且標(biāo)準(zhǔn)描述能夠轉(zhuǎn)換為數(shù)字表示，稱為描述數(shù)字。同樣的，以這種方式進(jìn)行轉(zhuǎn)換，每個單個的指令能夠從描述數(shù)字中找回。一個標(biāo)準(zhǔn)描述轉(zhuǎn)換為描述數(shù)字的方法是將標(biāo)準(zhǔn)描述中的“A C D L R N ；”分別轉(zhuǎn)換為“1 2 3 4 5 6 7”，這樣，每一個標(biāo)準(zhǔn)描述都可被轉(zhuǎn)換為描述數(shù)字。需要注意的是不同的標(biāo)準(zhǔn)描述能夠描述同一個機(jī)器的行為，如，將兩行規(guī)則表相互交換，這將不會影響機(jī)器在規(guī)則表下操作的行為，但是這將對接下來所得到的標(biāo)準(zhǔn)描述及其描述數(shù)字帶來影響。

從上述情況可以看出，將一個規(guī)則表轉(zhuǎn)換為一個標(biāo)準(zhǔn)描述或描述數(shù)字的這個過程類似于將一個計算機(jī)程序匯編為機(jī)器碼的過程。程序設(shè)計者通常會選擇在高階語言中如Pascal、Prolog和C語言中工作。圖靈所提到的規(guī)則表在高階語言中匯編對于一個受過培訓(xùn)的人來說是相當(dāng)簡單的，在一個程序開始執(zhí)行之前，指令碼必須被翻譯或者匯編為能夠被電腦接受的形式(機(jī)器碼)。

其三，是圖靈對通用計算機(jī)及其運作的論述。圖靈所說的通用計算機(jī)現(xiàn)在被稱為通用圖靈機(jī)，通用圖靈機(jī)是存儲程序電子計算機(jī)(現(xiàn)代計算機(jī))的抽象概念形式。不是所有圖靈機(jī)都是通用的，有一些圖靈機(jī)只能執(zhí)行某些特定的計算，只有通用圖靈機(jī)才能夠完成最一般的計算。能夠模擬其他任何圖靈機(jī)的圖靈機(jī)稱為通用圖靈機(jī)，亦即通用計算機(jī)。通用計算機(jī)有一個單一、固定的指令規(guī)則表。在這個指令規(guī)則表下運行，通用計算機(jī)能夠執(zhí)行任何任務(wù)，并且其指令規(guī)則表都能夠被寫出來。

當(dāng)我們談到計算機(jī)程序的時候，它是有輸入和輸出的。讀取一段程序即是輸入，將得到的結(jié)果寫出來即是輸出。但是，圖靈機(jī)是只有輸出而沒有輸入的，原因是圖靈機(jī)開始工作于一條無限長的空白紙帶，輸出數(shù)字?jǐn)?shù)列和其他的一些符號。而通用計算機(jī)與圖靈機(jī)不同，通用計算機(jī)要求在開始工作前輸入某一臺機(jī)器的標(biāo)準(zhǔn)描述，會寫出和該臺機(jī)器一樣的輸出，因此通用計算機(jī)相對于圖靈機(jī)來說更為普遍、一般。

通用計算機(jī)是有一定復(fù)雜性的，然而，就如圖靈所說的一樣，通用計算機(jī)的最根本原則就是簡單。以下為載入某個規(guī)則表指令的圖靈機(jī)(這時機(jī)器的掃描儀處于計算機(jī)紙帶的起始處，并且紙帶是完全空白的)的例子，如果將一個機(jī)器的標(biāo)準(zhǔn)描述放置于通用計算機(jī)的紙帶上，那么在紙帶上特別標(biāo)記的區(qū)域，通用計算機(jī)所輸出的數(shù)列也是這個機(jī)器所輸出的。通用計算機(jī)在它的紙帶上以閱讀指令來這樣做，標(biāo)準(zhǔn)描述包括而且執(zhí)行它們。為了使通用計算機(jī)工作，我們需要將這個機(jī)器的標(biāo)準(zhǔn)描述、初始狀態(tài)和初始掃描區(qū)域的符號放在紙帶上，除此之外，紙帶上的其他區(qū)域都是空白的。然后，給該機(jī)器一個運行的刺激，則機(jī)器將會在紙帶上留下一個記錄。與圖靈機(jī)不同的是，在紙帶上不僅會有通用計算機(jī)所寫的符號，而且還有計算時掃描儀每一步的位置、掃描儀顯示的符號和每一步的狀態(tài)。

圖靈想要給通用計算機(jī)下一個普遍定義，他對數(shù)學(xué)過程能夠被這種類型的計算機(jī)所實現(xiàn)進(jìn)行了嚴(yán)謹(jǐn)?shù)姆治?，他還介紹和分析了通用計算機(jī)的概念，如果任何數(shù)列能夠被任何計算機(jī)所輸出并且能夠被這種特別的計算機(jī)所解決，則這個計算機(jī)便是通用的。一般而言，為了達(dá)到這個目的，它需要將不同的指令組合起來。這是圖靈理論的主要成果[6]。

三、圖靈可計算數(shù)思想的當(dāng)代影響

馮·諾依曼和紐曼深受圖靈的通用存儲計算機(jī)理念的影響，這兩位數(shù)學(xué)家和圖靈本人是將圖靈的抽象通用計算機(jī)變?yōu)楝F(xiàn)實的重要電子計算機(jī)工程師。

在第二次世界大戰(zhàn)之后的幾年，邏輯學(xué)家、數(shù)學(xué)家馮·諾依曼通過他的文章和公眾演講，使得存儲程序數(shù)字計算機(jī)的概念廣為流傳。

1933年，馮·諾依曼開始在普林斯頓大學(xué)的一個高級研究院擔(dān)任教授，馮·諾依曼和圖靈第一次見面是在1935年4月，他與圖靈相熟識是圖靈在普林斯頓大學(xué)學(xué)習(xí)期間。圖靈在普林斯頓大學(xué)的這段時間，馮·諾依曼對“論可計算數(shù)”的理論逐漸熟悉起來，他逐漸對圖靈的通用計算機(jī)的概念變得很有興趣。馮·諾依曼在他的論文《計算機(jī)和大腦》[7]中提到兩個名字，其中一個是圖靈，另一個是信息論的提出者克勞德·香農(nóng)。顯然，馮·諾依曼對圖靈所做的工作是滿懷敬意的。

物理學(xué)家富蘭克爾(他和馮·諾依曼及其他人在參與自動化和氫彈的設(shè)計中使大型計算機(jī)機(jī)械化)記錄了在馮·諾依曼思想中“論可計算數(shù)”的重要地位，大約在1943年或1944年，馮·諾依曼已經(jīng)意識到圖靈的《論可計算數(shù)在判決性問題中的應(yīng)用》的重要地位，這篇文章在原則上描述了“通用計算機(jī)”，每一臺生產(chǎn)出的計算機(jī)都是它現(xiàn)實化的版本。許多人都認(rèn)為馮·諾依曼是“計算機(jī)之父”(在現(xiàn)在的眼光看來)，但是可以肯定的是馮·諾依曼從沒有這樣認(rèn)為過。馮·諾依曼被稱為計算機(jī)的助生者可能更為恰當(dāng)，馮·諾依曼堅定地向所有人強(qiáng)調(diào)，最基本的概念屬于圖靈。因此，在筆者看來，馮·諾依曼的貢獻(xiàn)就是使世界認(rèn)識到圖靈所介紹的計算機(jī)的基本概念，以及對摩爾學(xué)校(the Moor School)和其他地方的計算機(jī)發(fā)展所起的促進(jìn)作用[8]。

1949年，在伊利諾斯州大學(xué)的一個名為“控制和信息的嚴(yán)謹(jǐn)理論”的演講中，馮·諾依曼談及圖靈的研究的重要之處在于：如果你構(gòu)建好了一臺自動機(jī)，然后關(guān)于自動機(jī)的任何附加要求都能夠以足夠詳盡說明的指令來處理。如果自動機(jī)足夠復(fù)雜，并且它已經(jīng)到達(dá)了最低要求的復(fù)雜性，那么這就是真的。換句話說，在給定合適的指令下，這種復(fù)雜的自動機(jī)能夠做任何能被這個自動機(jī)執(zhí)行的事情[9]。

馮·諾依曼將圖靈的“通用計算機(jī)”的抽象概念介紹給許多美國工程師，但是在美國許多關(guān)于計算機(jī)歷史的書中都沒有提及圖靈。毫無疑問，在許多技術(shù)性的報告中，關(guān)于計算機(jī)歷史都沒有涉及到圖靈所做的工作，但馮·諾依曼和其他的合作者將邏輯性的設(shè)計融入了電子存儲數(shù)字計算機(jī)之中，有證據(jù)證明在馮·諾依曼的文獻(xiàn)中有關(guān)于“論可計算數(shù)”的知識。例如，在“電子計算機(jī)邏輯設(shè)計的初級討論”的報告中，馮·諾依曼提到：“以形式邏輯的方法很容易看出，在理論上足夠去控制和使其去執(zhí)行的任何各自可適用于機(jī)器的操作數(shù)列出現(xiàn)的代碼，在整體上都會被問題計劃者所想到。從目前來看，在選擇代碼時的真正決定性的考慮因素更多的是一種現(xiàn)實性：設(shè)備的簡易性由機(jī)器碼所決定，和其應(yīng)用到實際的重要問題的清晰度和處理問題的這些問題?！盵10]這篇文章的第一句話就涉及到了圖靈的通用計算機(jī)。

圖靈對于現(xiàn)代計算機(jī)發(fā)展最為重要的貢獻(xiàn)是控制一臺計算機(jī)運行是通過存儲一個代表性的程序，然后在計算機(jī)的內(nèi)存中將程序編碼為指令的理念；而且他證明用這種方法，一臺固定架構(gòu)的單一計算機(jī)能夠執(zhí)行每一個計算，并且這些計算能夠被任何一臺圖靈機(jī)執(zhí)行，也就是通用的。

圖靈描述了通用計算機(jī)和存儲程序電子計算機(jī)(現(xiàn)代計算機(jī))之間的聯(lián)系:有一種重要機(jī)制的機(jī)器包含無限紙帶的存儲空間，這表明這種單一特殊的機(jī)器能夠做任何工作，這種特殊的機(jī)器可以被稱為通用機(jī)器。當(dāng)我們決定希望模仿怎樣的機(jī)器時，我們就在通用計算機(jī)的紙帶上給予它一個該機(jī)器的描述，這個描述解釋了機(jī)器在每一個格局中將會如何做，在哪兒可以找到自己。通用計算機(jī)為了知道它在每一個階段需要怎么做，它只有在這個給定的描述上不停地尋找適合當(dāng)前格局的指令。因此，這個機(jī)器所做的工作的復(fù)雜性就是“集中于紙帶上”(為指令規(guī)則表，其實就是軟件)，“而且不應(yīng)該以任何方式出現(xiàn)在通用機(jī)器中”[11]。

圖靈所使用的用于圖靈機(jī)的指令規(guī)則表就是現(xiàn)在稱為計算機(jī)的程序。當(dāng)他轉(zhuǎn)而去設(shè)計一臺電子計算機(jī)(ACE)時，圖靈繼續(xù)使用他的“指令規(guī)則表”這個概念，而現(xiàn)在的作者們用“程序”來代替它。類似ACE這樣的計算機(jī)實際上是更加實際的通用機(jī)器，有一個確定的電子設(shè)備的核心區(qū)域和一個大的存儲，當(dāng)任何詳細(xì)的問題需要被解決的時候，計算過程的合適指令將會存儲在ACE的內(nèi)存中，然后它就會運行來執(zhí)行這個過程。

最初，圖靈提出以十六進(jìn)制來對將要輸入計算機(jī)的指令進(jìn)行編碼，隨著不斷深入寫程序的過程，他發(fā)現(xiàn)以二進(jìn)制的形式來對其進(jìn)行編碼更為合適。就大規(guī)模的計算而言，使用二進(jìn)制是很自然的事，在使用二進(jìn)制之后，計算更為簡單，因為制定只有兩個固定位置的機(jī)制比制定多達(dá)十幾個的固定位置的機(jī)制要容易得多[11]。然而，實際上真正重要的是，既然機(jī)器能夠像人類那樣執(zhí)行計算且計算是人類思維的基本組成部分，那么機(jī)器是否能像人類一樣思維呢？在圖靈看來，這個答案是不言而喻的，他所提出的計算機(jī)在本質(zhì)上與大腦并沒有什么區(qū)別。

由大腦的生理構(gòu)成我們可以看到，人類的大腦是由大量被稱為神經(jīng)元的成分組成，科學(xué)家們估計神經(jīng)元的數(shù)量多達(dá)10億或更多。這些神經(jīng)元通過軸突和樹突組成密集有線網(wǎng)絡(luò)互相連接，就如一個巨大的網(wǎng)交織在一起，神經(jīng)元可以看作為一種基本的開關(guān)，在任何情況下它都處于“開”或“關(guān)”的狀態(tài)中。到底處于哪個狀態(tài)取決于與它相連的其他神經(jīng)元傳來的信號。由此可以看出，計算機(jī)與大腦都能存儲大量的基本數(shù)據(jù)，在計算機(jī)中是紙帶上的0和1，而在神經(jīng)元中是開和關(guān)的狀態(tài)，關(guān)鍵是它們都能將這些數(shù)據(jù)處理成為某種模式。大腦的數(shù)據(jù)將以模式的形式來存儲，這個模式是由神經(jīng)元受到刺激而激發(fā)機(jī)制產(chǎn)生的。每種模式實際上是在某一時刻神經(jīng)元的“開”和“關(guān)”的狀態(tài)。而對于計算機(jī)來說，其數(shù)據(jù)存儲在內(nèi)存之中，其模式就是0和1的序列，這與狀態(tài)的“開”和“關(guān)”沒有區(qū)別。

大腦與計算機(jī)都能修改存儲的值，前者通過不同的神經(jīng)元被刺激，后者通過程序指令的修改。計算機(jī)相應(yīng)于大腦的存儲行為以及模式的改變是非常相似的。而正是這種相似性使得圖靈相信在不久的將來可以建造出一臺可以思維的機(jī)器。唯一的障礙不是在邏輯上，而是在技術(shù)上。從人類智能行為上來看，我們大腦的構(gòu)成材料并沒有什么特殊的物質(zhì)，至少是在與思想有關(guān)的范圍之中是這樣的。從某種角度看來組成大腦的物質(zhì)并非是真正的問題，真正的問題在于大腦的基本原件神經(jīng)元究竟做了什么以及它們彼此怎樣互相聯(lián)系，才使得大腦具有認(rèn)知能力。正是鑒于此，圖靈提出了“模仿游戲”，即如果一臺計算機(jī)被編程去和一個相當(dāng)聰明的人進(jìn)行一段對話，不管談話提出的主題是否是有效的，只要無法簡單地判斷在與他或她談話的是一個人或者是一個機(jī)器，圖靈就說我們應(yīng)該同意該計算機(jī)表現(xiàn)出了智能。從提出至今，圖靈的模仿游戲招致了無數(shù)的爭議，塞爾曾提出“中文屋”以反駁圖靈；休·羅布納在20世紀(jì)90年代初設(shè)立了人工智能年度比賽，將圖靈的“模仿游戲”付諸行動；在不久之前，圍棋人工智能程序AlphaGo在圍棋比賽中成功戰(zhàn)勝世界冠軍李世石。然而直至現(xiàn)在，并沒有一臺機(jī)器可以通過圖靈的“模仿游戲”測試，也沒有任何測試可以取代模仿游戲成為機(jī)器能思維的標(biāo)準(zhǔn)測試。作為機(jī)器能思維的充分條件，圖靈測試依然是人類實現(xiàn)自身以外智能而一直追求的目標(biāo)。

圖靈是一個對于現(xiàn)代社會有相當(dāng)影響的人物，他論文中提出的“計算機(jī)”和“算法”兩個核心概念在今天依然受用，他的“模仿游戲”測試依然作為測試機(jī)器能否思維的一個標(biāo)準(zhǔn)，他的通用計算機(jī)的設(shè)計理念和指令規(guī)則表的使用為后世計算機(jī)科學(xué)及其相關(guān)領(lǐng)域的發(fā)展奠定了基礎(chǔ)，并使現(xiàn)代以信息為主導(dǎo)的社會的出現(xiàn)成為可能。

[1] HINSLEY H,STRIPP A.Codebreakers:the inside story of bletchley park[M].Oxford:Oxford University Press,1993:12.

[2] 馬丁·戴維斯.邏輯的引擎[M].張卜天,譯.長沙：湖南科學(xué)技術(shù)出版社，2006：64-65.

[3] TURINGA.On computable numbers,with an application to the entscheidungsproblem[G].Proceedings of the London Mathematical Society,1936:230-265.

[4] TURINGA.The t-function in λ-K-conversion[J].the Journal of Symbolic Logic,1937(2):42-43.

[5] MARTIN D.Mathematical logic and the origin of modern computers[M].Oxford:Oxford University Press,1988:149-174.

[6] VON NEUMANN J.The general and logical theory of automata[R].to be published.

[7] VON NEUMANN J.The computer and the brain[M].New Haven:Yale University Press,1958.

[8] RANDELL B.On Alan Turing and the origins of digital computers[M].[S.l.]:University of Newcastle upon Tyne,Computing Laboratory,1972.

[9] VON NEUMANN J.Rigorous theories of control and information[G]//Theory of Self-Reproducing Automata.Urbana:University of Illinois Press,1966:50.

[10]BURKS A W,GOLDSTINE H H,VON NEUMANN J.Preliminary discussion of the logical design of an electronic computing instrument[G]//The Origins of Digital Computers.[S.l.]:Springer Berlin Heidelberg,1982:399-413.

[11]CARPENTER B E,DORAN R W.AM Turing’s ACE report of 1946 and other papers[M].[S.l.]:Massachusetts Institute of Technology,1986.

(責(zé)任編輯 張佑法)

Discussion of Turing’s Computable Thought

HU Song

(College of Marxism,Central China Normal University, Wuhan 430070,China)

Turing’s computable thought has profound ideological origins, and the developments of Leibniz,Frege and Godel for artificial language has affected computable thought of Turing.The paperOncomputablenumbers,withanapplicationtotheEntscheidungsproblemhas proposed two abstract machines:Turing machine and general-purpose computer,and described basic structure and operation mode of both machines.Among them,general-purpose computer is the prototype of the modern computer;Turing’s computable thought fundamentally affected Von Neumann and thushelped him constructed the first computer. There is no substitute for Turing’s contribution to the development of the modern computer and machine intelligence.

computable thought;Turing machine;all-purpose computer;modern computer;machine thought

2016-09-12 作者簡介：胡嵩(1991—)，男，湖北鄂州人，碩士研究生，研究方向：科學(xué)邏輯。

胡嵩.論圖靈的可計算思想[J].重慶理工大學(xué)學(xué)報(社會科學(xué))，2016(11):32-37.

format：HU Song.Discussion of Turing’s Computable Thought[J].Journal of Chongqing University of Technology(Social Science)，2016(11):32-37.

10.3969/j.issn.1674-8425(s).2016.11.004

B81-05

A

1674-8425(2016)11-0032-06