第2章　計算機(jī)祖孫三代

2.1　計算機(jī)爺爺——圖靈機(jī)模型

2.1.1　艾倫·圖靈是個科學(xué)家

艾倫·圖靈（Alan Turing，1912—1954）如圖2-1所示。這個名字無論是在計算機(jī)領(lǐng)域、數(shù)學(xué)領(lǐng)域、人工智能領(lǐng)域還是哲學(xué)、邏輯學(xué)等領(lǐng)域，都可謂擲地有聲。艾倫·圖靈是計算機(jī)邏輯的奠基者，許多人工智能的重要方法也源自這位偉大的科學(xué)家。

100多年前，艾倫·圖靈誕生在一個文化和科技水平都與現(xiàn)在完全不同的時代里，他為計算機(jī)領(lǐng)域奠定了不可埋沒的基礎(chǔ)，沒有他就沒有計算機(jī)的今天。

他在24歲時提出了圖靈機(jī)理論，31歲時參與了Colossus（第二次世界大戰(zhàn)時，英國破解德國通信密碼的計算機(jī)）的研制，33歲時構(gòu)思了仿真系統(tǒng)，35歲時提出自動程序設(shè)計概念，38歲時設(shè)計了“圖靈測試”；在后來還創(chuàng)造了一門新學(xué)科——非線性力學(xué)。他的業(yè)余愛好是長跑，如圖2-2所示。

雖然艾倫·圖靈去世時只有42歲，但在其短暫而離奇的生涯中的那些科技成就，已讓后人享用不盡。人們仰望著這位偉大的英國科學(xué)家，把他稱為“計算機(jī)之父”“人工智能之父”“破譯之父”，有人甚至認(rèn)為，他在技術(shù)上的貢獻(xiàn)及對未來世界的影響幾乎可與牛頓、愛因斯坦等巨人比肩。

1936年，還在劍橋國王學(xué)院就讀的艾倫·圖靈發(fā)表重要論文《論可計算數(shù)及其在判定問題上的應(yīng)用》（On Computable Numbers，with an Application to the Entscheidungsproblem），提出“算法（algorithm）”和“計算機(jī)（computing machine）”兩個核心概念，一直讓人們受用到今天。

當(dāng)時的圖靈機(jī)還只能計算有限的實(shí)數(shù)，但它的符號記錄方法為以后的計算機(jī)發(fā)展奠定了基礎(chǔ)理論，基于此，人類首次產(chǎn)生了符號處理的概念，并開始把研究重點(diǎn)轉(zhuǎn)向可改變的編碼程序，這就是今天軟件的前身。

1939年第二次世界大戰(zhàn)爆發(fā)，正在為英國國家密碼機(jī)構(gòu)工作的艾倫·圖靈和其他科學(xué)家一起著手研究如何破解敵人的密碼，他果然不負(fù)眾望，成功破譯了德國軍方使用的著名通信密碼系統(tǒng)Enigma（謎）。于是第一臺電子圖靈機(jī)被設(shè)計制造出來，做出重大貢獻(xiàn)的艾倫·圖靈獲得了政府頒發(fā)的OBE獎。

1946年，艾倫·圖靈發(fā)表論文闡述存儲程序計算機(jī)的設(shè)計。他的成就與研究離散變量自動電子計算機(jī)（Electronic Discrete Variable Automatic Computer）的約翰·馮·諾依曼（John von Neumann）同期。艾倫·圖靈的自動計算機(jī)與約翰·馮·諾依曼的離散變量自動電子計算機(jī)都采用二進(jìn)制，都以“內(nèi)存儲存程序以運(yùn)行計算機(jī)”打破了那個時代的舊有概念。

1950年，艾倫·圖靈的一篇里程碑式的論文《機(jī)器能思考嗎？》又為人類帶來了一個新學(xué)科——人工智能。為了證明機(jī)器是否能夠思考，他又發(fā)明了“圖靈測試”（Turing Test），圖靈測試在今天仍被沿用。他指出，最好的人工智能研究應(yīng)該著眼于為機(jī)器編制程序，而不是制造機(jī)器。而他在論文中預(yù)測的計算機(jī)發(fā)展過程中將會出現(xiàn)的一些問題，至今仍未被解決。

2.1.2　圖靈機(jī)模型

學(xué)習(xí)計算機(jī)科學(xué)的讀者都應(yīng)該知道，在計算機(jī)基礎(chǔ)理論中有著名的“圖靈機(jī)”和“圖靈測試”。這些理論簡潔地概括了圖靈偉大貢獻(xiàn)的一部分：他是第一個提出利用某種機(jī)器實(shí)現(xiàn)邏輯代碼的執(zhí)行，以模擬人類的各種計算和邏輯思維過程的科學(xué)家。而這一點(diǎn)，成為后人設(shè)計實(shí)用計算機(jī)的思路來源，成為當(dāng)今各種計算機(jī)設(shè)備的理論基石。當(dāng)今計算機(jī)科學(xué)中再常用不過的程序語言、代碼存儲和編譯等基本概念，就是來自艾倫·圖靈的原始構(gòu)思。

圖靈機(jī)（Turing Machine）又稱為圖靈計算機(jī)，是艾倫·圖靈提出的一種抽象計算模型，即將人們使用紙和筆進(jìn)行數(shù)學(xué)運(yùn)算的過程進(jìn)行抽象，由一個虛擬的機(jī)器替代人們進(jìn)行數(shù)學(xué)運(yùn)算。

圖靈機(jī)是一個抽象的機(jī)器，它有一條無限長的紙帶，紙帶分成一個一個的小方格，每個方格有不同的顏色；有一個機(jī)器頭在紙帶上移來移去。機(jī)器頭有一組內(nèi)部狀態(tài)，還有一些固定的程序。在每個時刻，機(jī)器頭都要從當(dāng)前紙帶上讀入一個方格信息，然后結(jié)合自己的內(nèi)部狀態(tài)查找程序表，根據(jù)程序輸出信息到紙帶方格上，并轉(zhuǎn)換自己的內(nèi)部狀態(tài)，然后進(jìn)行移動。

2.1.3　計算機(jī)界的諾貝爾獎

圖靈獎（Turing Award）是美國計算機(jī)協(xié)會（ACM）于1966年設(shè)立的，專門獎勵那些對計算機(jī)事業(yè)做出重要貢獻(xiàn)的個人。其名稱取自世界計算機(jī)科學(xué)的先驅(qū)、英國科學(xué)家、英國曼徹斯特大學(xué)艾倫·圖靈，這個獎設(shè)立目的之一是紀(jì)念這位現(xiàn)代計算機(jī)奠基者。獲獎?wù)弑仨毷窃谟嬎銠C(jī)領(lǐng)域具有持久且重大的先進(jìn)性的技術(shù)貢獻(xiàn)。大多數(shù)獲獎?wù)呤怯嬎銠C(jī)科學(xué)家。

圖靈獎是計算機(jī)界最負(fù)盛名的獎項(xiàng)，有“計算機(jī)界的諾貝爾獎”之稱。圖靈獎對獲獎?wù)叩囊髽O高，評獎程序也極嚴(yán)，一般每年只獎勵一名計算機(jī)科學(xué)家，只有極少數(shù)年度有兩名以上在同一方向上做出貢獻(xiàn)的科學(xué)家同時獲獎。