本節書摘來自華章計算機《計算複雜性：現代方法》一書中的第1章，第1.7節，作者 ［美］桑傑夫·阿羅拉（sanjeev arora），博阿茲·巴拉克（boaz barak），譯 駱吉洲，更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。
本章學習内容
●存在許多等價方法對計算過程進行數學模組化。我們采用标準的圖靈機定義。
●圖靈機可以表示為位串。存在通用圖靈機，它可以（代價很小地）模拟任意給定的用位串表示的圖靈機。
●存在函數不能被任意圖靈機計算，不管計算時間多長。停機問題是不可計算的。
●類p是由可以被圖靈機在多項式時間内求解的所有判定問題構成的。我們稱p中的問題是可以被高效求解的。
●圖靈機定義中(帶的數量、字母表大小等)底層結構的選取不是本質的，因為它們不會改變p的定義。
本章注記和曆史
盡管算法的研究已持續千百年，并且一些計算裝置也早在二十世紀以前就被發明出來（最值得關注的是十九世紀中葉由查爾斯·巴貝奇(charles babbage)發明的差分機和分析機）。但确切地講，現代計算機科學的基礎直到二十世紀三十年代才真正奠定。
1931年，庫爾特·哥德爾證明了在自然數上肯定成立的命題是固有的不可證明的，這一結果震驚了整個數學界，同時粉碎了希爾伯特在1900年提出的旨在建立完備算術公理的雄心勃勃的研究計劃。1936年，阿隆佐·邱奇（alonzo church）定義了一種稱為λ演算的計算模型（多年後由此産生了lisp這種程式設計語言），并證明了該計算模型上存在固有的不可計算函數［chu36］。幾個月之後，阿蘭·圖靈獨立地引入了他的圖靈機，并證明了圖靈機上也存在固有的不可計算函數［tur36］。圖靈還介紹了能加載任意程式的通用圖靈機的思想。前述的兩種計算模型已被證明是等價的。然而，正如邱奇自己所述，圖靈機的優點在于“根據普通意義（而非顯式的定義）就能立即明确地認定高效性”。文集［dav65］收錄了可計算理論方面的許多影響深遠的開創性論文。西普賽爾(sipser)的書［sip96］的第二部分很好地對可計算理論作了一般性介紹，而［rog87,hmu01,koz97］等書則相對深入地對此進行了讨論。這些書也涵蓋了自動機理論，它是計算理論的另一個領域，本書目前未做相關讨論。本書網站提供了可計算理論和自動機理論相關資訊的連結。
二戰期間，圖靈設計了機械密碼破譯裝置，它在破譯德軍的“謎”密碼的過程中發揮了關鍵作用，同時該項成就也改變了戰争的程序（參見傳記［hod83,lea05］）。二戰後，建造通用電子計算機的任務在英國和美國同時進行，建造過程的一個關鍵人物是約翰·馮·諾依曼。這位極其多産的科學家除參加了曼哈頓項目的整個過程之外，還發現了經濟博弈論。截止到目前，所有的數字計算機本質上均采用了“馮·諾依曼體系結構”，這是由他在設計最早的數字計算機edvac的過程中提出的［vn45］。