第2章　計算機祖孫三代

2.1　計算機爺爺——圖靈機模型

2.1.1　艾倫·圖靈是個科學家

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

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

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

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

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

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

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

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

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

2.1.2　圖靈機模型

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

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

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

2.1.3　計算機界的諾貝爾獎

圖靈獎（Turing Award）是美國計算機協會（ACM）于1966年設立的，專門獎勵那些對計算機事業做出重要貢獻的個人。其名稱取自世界計算機科學的先驅、英國科學家、英國曼徹斯特大學艾倫·圖靈，這個獎設立目的之一是紀念這位現代計算機奠基者。獲獎者必須是在計算機領域具有持久且重大的先進性的技術貢獻。大多數獲獎者是計算機科學家。

圖靈獎是計算機界最負盛名的獎項，有“計算機界的諾貝爾獎”之稱。圖靈獎對獲獎者的要求極高，評獎程序也極嚴，一般每年只獎勵一名計算機科學家，只有極少數年度有兩名以上在同一方向上做出貢獻的科學家同時獲獎。