2.2.1 圖靈機的起源

提出圖靈機的人是艾倫·圖靈（Alan Turing）[見圖2.19（a）]，他于1912年在英國倫敦出生，1931年開始在劍橋大學主修數學專業，1934年本科畢業并以優異的成績獲得學士學位。1935年，他繼續在劍橋大學攻讀碩士學位，并在此期間提出了圖靈機的概念。1936年，圖靈前往美國普林斯頓大學深造，師從阿隆佐·丘奇（Alonzo Church），并在1938年獲得數學博士學位。在圖靈讀博士期間，馮·諾依曼[見圖2.19（b）]已經是普林斯頓大學的量子力學教授，他對圖靈提出的圖靈機非常感興趣，并邀請他做自己的助理，但圖靈婉言謝絕，并在畢業后回到英國工作。馮·諾依曼基于圖靈機及基本電子元器件，創立了當今電子計算機的體系結構。圖靈對理論計算機科學的發展貢獻巨大，被稱為理論計算機科學之父，故計算機領域的最高獎被命名為圖靈獎。

（a）　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（b）

圖2.19　艾倫·圖靈與馮·諾依曼

（a）艾倫·圖靈　（b）馮·諾依曼

圖靈在于1936年發表的論文《論可計算數及其在判定性問題上的應用》（On Computable Numbers, with an Application to the Entscheidungsproblem）[21]中提出了與阿隆佐·丘奇相似的可計算性的概念，并且證明了希爾伯特判定性問題是無解的。在證明過程中，圖靈定義了幾種計算機器，其中的自動機就是圖靈機的前身。這篇論文被稱為“歷史上最具影響力的數學論文”之一。

實際上，對“可計算性”的研究可追溯到1904年，當時大衛·希爾伯特（David Hilbert）提出了把數學證明本身作為數學對象來研究。1922年，他在德國漢堡的一次會議上提出了他的證明論研究規劃，稱為希爾伯特規劃。該規劃將具體的數學理論與所用到的邏輯同時公理化，從而形成形式系統。希爾伯特規劃展示了一項激動人心的事業，即“一勞永逸地消除任何對數學基礎可靠性的懷疑”。除了希爾伯特，這項事業還吸引了一批青年數學家，如威廉·阿克曼（Wilhelm Ackermann）與馮·諾依曼等。1931年，庫爾特·哥德爾（Kurt G?del）證明了任何包含一階謂詞邏輯和初等數論的形式系統都是不完備的，從而否定了希爾伯特規劃。1935年春到1936年春，圖靈和阿隆佐·丘奇同時從哥德爾不完備定理開始研究問題的可判定性。1936年5月28日，圖靈在《倫敦數學學會會刊》上分兩部分發表了《論可計算數及其在判定性問題中的應用》，文中重新表述了哥德爾在1931年的成果，并提出了確定型圖靈機、非確定型圖靈機和通用圖靈機的概念。圖靈機后來成為可計算理論和計算復雜性理論的基礎。

1938年，圖靈在他的博士論文《基于序數的邏輯系統》（Systems of Logic based on Ordinals）[22]中引入了序數邏輯和相對計算的概念，拓展了數理邏輯的研究領域。除了純數學工作，圖靈還研究了密碼學，并構建了機電二進制乘法器。在第二次世界大戰期間，圖靈在布萊切利莊園的政府密碼學校工作，布萊切利莊園是英國的密碼破譯中心，曾破譯出極為重要的情報。圖靈設計了加速破譯德國密碼的技術，構建了一種可以破譯用恩尼格瑪密碼機加密的信息的機電裝置。他在破解截獲信息方面做出了極大的貢獻，幫助盟軍在包括大西洋戰役在內的多次關鍵戰役中獲勝。戰后，圖靈在英國國家物理實驗室工作，設計了自動計算機，這是最早的存儲程序計算機。1948年，圖靈加入維多利亞大學馬克斯·紐曼（Max Newman）的計算機實驗室，幫助開發了曼徹斯特計算機，并對數學生物學產生了興趣。之后，圖靈的研究涉及生物計算和模式形成，對早期的機器學習和計算生物學產生了重要影響。此外，圖靈還撰寫了關于形態發生的化學基礎的論文并預測了振蕩化學反應，他提出的圖靈測試至今仍被視為判斷機器智能的標準。

下面介紹圖靈機的原理、類型（包括確定性圖靈機、非確定性圖靈機及相關變體），它們在理論上是等效的，即具有圖靈等價性。