胡 嵩

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

?

論圖靈的可計(jì)算思想

胡 嵩

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

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

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

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

一、圖靈可計(jì)算思想的淵源

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

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

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

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

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

二、圖靈的可計(jì)算思想的主要觀點(diǎn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[2] 馬丁·戴維斯.邏輯的引擎[M].張卜天,譯.長(zhǎng)沙：湖南科學(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 作者簡(jiǎn)介：胡嵩(1991—)，男，湖北鄂州人，碩士研究生，研究方向：科學(xué)邏輯。

胡嵩.論圖靈的可計(jì)算思想[J].重慶理工大學(xué)學(xué)報(bào)(社會(huì)科學(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