計算理論基礎（第2版）

《計算理論基礎（第2版）》是2006年清華大學出版社出版的圖書，作者是張立昂。

內容簡介

計算理論是計算機科學的理論基礎。本書介紹了計算理論最核心、最基本的內容，包括形式語言與自動機、可計算性和計算複雜性三大部分。全書共分7章，分別為：集合、關係和語言；有窮自動機；上下文無關語言；Turing機；不可判定性；計算複雜性；NP完全性。本書突出了算法，從而使計算機專業的學生更易於接受，也更有收益。

本書適合作為計算機專業及數學專業本科生或研究生的教材，也可供從事計算機科學的教學與研究人員參考。

前言

半年前我先後接到清華大學出版社第四編輯室室主任薛慧同志和機械工業出版社華章圖文信息有限公司總編輯傅豫波同志的電話，前者請我翻譯這本書，後者請我翻譯Sipser的Introduction to the Theory of Computation (Second edition)，我都欣然接受，並且邀請王捍貧、劉田和黃雄三位博士共同翻譯。其實，翻譯教材並不是一件美差，對我來說，更談不上是“好事”，由於眼疾，看書時間一長，心裡總犯怵。現在總算完成了任務，兩本書都即將出版(儘管中間眼睛還是又犯了一次病)。我之所以願意翻譯這兩本書，一是因為它們確實是兩本關於計算理論的優秀教材；二是因為國內太缺乏這樣的書了，儘管計算機類書刊極其繁多，可是計算理論的書卻難覓蹤影。清華大學出版社和華章圖文信息有限公司購買這兩本書的著作權翻譯出版，此乃善舉!我怎好推卻。

計算理論在計算機科學技術專業的教學計畫中的地位是有爭議的。國內計算機專業本科幾乎沒有開計算理論課的，研究生學這門課的好像也不多，倒是那些想去美國讀書的學生為了應付GRE Subject測試，自己在找有關計算理論的書看。我希望這兩本書的出版能有利於提高計算機教育界對計算理論的重視，特別希望立志致力於計算機科學技術事業的青年學生都來認真地學一點計算理論，那將可能是終身受益的。

本書包括形式語言與自動機、可計算性和計算複雜性三大部分，這是計算理論最核心、最基本的內容。本書的一大特色是突出了算法，從語法分析到NP難問題的實用算法，算法貫穿全書。這些內容不僅透徹生動地提供了算法設計與分析的基本理論，而且使讀者清楚地看到，計算理論不是沒有用，也不是離實際很遠的。恰恰相反，不僅當今的許多計算機技術可以在計算理論中找到它的思想淵源，而且在許多實際問題中充滿著計算理論。

我們按照作者在第二版序言中提供的電子郵件地址得到本書的勘誤。在翻譯過程中我們又發現了一些錯誤，也都予以更正。這些錯誤基本上都是非實質性的，因此沒有在書中一一指明。我們已用電子郵件把發現的錯誤發給作者。

第一版序言

本書在大學本科水平上介紹經典的和當代的計算理論。粗略地說，內容包括自動機理論與形式語言、Turing(圖靈)機的可計算性與遞歸函式、不可計算性、計算複雜性以及數理邏輯，採用數學的處理方法和計算機科學的觀點。於是，在關於上下文無關語言的一章中包含語法分析的討論，在關於邏輯的幾章中給出定理歸結證明的有效性和完備性。

在本科教學計畫中，這門課通常安排在後面和算法設計與分析課同時上。我們的看法是學計算機科學的學生應該早一點接觸這些材料，比如，在二年級或三年級。這是因為，其一，對這些材料的深入研究形成計算機科學中的一些專題；其二，它有助於提供必要的數學示範。但是，我們發現由於一些更高級的教科書要求學生具有較好的數學基礎，教這門嚴格的大學生課是一項困難的任務。我們寫這本書的目的是用數學的語言、但不要求有專門的數學經驗使得這門課的實質易於被大學生們理解。

全書提供一學年的課程。我們都講過一個學期的課程，包括第1章到第6章的大部分內容，根據情況刪去了關於語法分析、遞歸函式及具體的不可解判定問題的部分內容，其他的選擇是可能的。例如，強調可計算性和機械邏輯基礎的課程可以很快地跳過第1章到第3章，集中力量講第4、6、8和9章。不管怎樣使用它，我們都強烈地希望本書對下一代計算機科學家的智力發展有所貢獻，在他們受教育的早期階段向他們介紹關於計算問題的新鮮的和有條理的思想。

我們借這個機會感謝所有讓我們從他們那兒學到東西的人，包括教師和學生。特別感謝Larry Denenberg和Aaron Temin校對早期的草稿，Michael Kahl 和 Oded Shmueli 作為助教對我們的幫助和建議。1980年春季，Albert Meyer 在MIT(麻省理工學院)用這本書的草稿講課，提出很好的批評和修改意見，對此我們表示衷心的感謝。當然，遺留下任何錯誤都應該由我們負責。Renate D’Arcangelo 以她特有的、非凡的完美和迅速打手稿和畫圖。

第二版序言

自《計算理論基礎》問世以來，在這15年中許多東西變了，也有許多東西沒有變。計算機科學現在是一門成熟得多的公認的學科，在這個計算無處不在、信息全球化和複雜性迅速增長的世界上扮演越來越重要的角色，因此有更多的理由關心它的基礎。《計算理論基礎》的作者們自己現在更加成熟和忙碌——這是何以這么久才出第二版的原因。我們寫第二版，是因為我們感覺到有幾處可以說得更好些，有幾處可以簡單些，還有一些可以刪掉。更重要的是，我們希望本書反映計算理論和學它的學生在這些年的進步。雖然就絕對而言現在教計算理論的比過去多了，但是它在計算機科學教學計畫中的相對地位，例如與算法課程相比，沒有得到加強。實際上，算法設計與分析領域現在已經很成熟，有理由認為它的基本原理是關於計算理論的基礎課程的一部分。此外，今天的大學生有廣泛的和早期的計算經驗，清楚地知道自動機在編譯程式中的套用。但是，例如在講像Turing(圖靈)機這樣的簡單模型，用它們作為一般的計算機模型時，他們的疑問更多。總之，對這些問題的處理需要作某些修改。

具體地說，與第一版的主要區別有：

·早在第1章就形式地介紹算法設計與分析的入門(與閉包有關)，並且算法問題的討論貫穿全書。在第2、3章有幾節討論與有窮自動機和上下文無關文法有關的算法問題(包括狀態最小化和上下文無關識別)。有關於NP完全問題的易解變形的算法，還有一節考察“對付NP完全性”的算法技術(特殊情況的算法、近似算法、回溯與分支定界、局部改進以及模擬退火算法)。

·第4章對Turing機的處理更形式化，模擬論證更加簡單和更加定量。引入隨機存取Turing機，以幫助跨越Turing機的笨拙與計算機和程式設計語言能力之間的鴻溝。

·第5章介紹不可判定性，包括某些遞歸函式論內容(到Rice定理為止)。介紹文法和遞歸數值函式，證明它們等價於Turing機，證明更加簡單。與上下文無關文法有關問題不可判定性的證明採用簡單的直接論證，而不求助Post對應問題。保留鋪磚問題，這個問題在NP完全性一章還要見到。

·處理複雜性的方式相當的新穎：在第6章，除多項式時間界限之外沒有定義其他時間界限——於是，P是接觸到的第一個複雜性類和概念。然後，用對角化方法證明存在不在P中的指數問題。同時介紹現實生活中的問題與它們的語言表示(兩者的區別被故意地弄模糊了)，廣泛地考察它們的算法問題。

·NP完全性是單獨的一章。在這一章中，有一組新的、廣泛的、我們認為有助於教學的NP完全性歸約，最後一個是正則表達式的等價問題——回到本書的第一個問題。正如上面所說，本書的最後一節是關於“對付NP完全性”的算法技術。

·在這個新版中刪去關於邏輯的幾章。這是一個困難的決定。作出這樣的決定有兩個原因：種種跡象表明，這幾章是本書過去讀得最少和教得最少的幾章；現在有幾本更好的論述這個題目的書。但是，在第6章將詳細地論述布爾邏輯和它的可滿足性問題。

·總的說來，證明和講解被簡化了，並且在一些關鍵的地方更加形式化。有幾處，如在上下文無關語言與下推自動機的等價性的證明中，把長篇技術性歸納陳述的證明改作習題。每一節的後面有幾個習題。

經過這些改動之後，現在有不只一種的方式講授本書的材料(還有在第一版中提出的方式以及使用中形成的方式)。以講授計算理論和算法的基礎為目標的一學期長的課程可以以從第2章到第7章中選取的材料為基礎。

我們衷心地感謝在這15年中所有向我們提供反饋、想法、錯誤和更正的我們的學生和同事——不可能在這裡把他們全部列出來。特別感謝Martha Sideri幫助修訂第3章。還要十分感謝本書的編輯Alan Apt 和 Prentice Hall的朋友們——Barbara Kraemer, Sondra Chavez 和 Bayani de Leon——他們都非常有耐心而且樂於助人。

導言

看看你的周圍，計算無處不在，無時不在，每一個人都計算，計算影響著所有的人。所以能夠如此，是因為在過去的幾十年中計算機科學家發現了很複雜的方法用來管理計算機資源，實現通訊，翻譯程式，設計晶片和資料庫，創造更快、更廉價、更容易使用、更安全的計算機和程式。

和所有的主要學科一樣，計算機科學的成功實踐建立在優美和堅實的基礎之上。自然科學有一些基本問題，如物質的本質是什麼?有機體生命的基礎和起源是什麼?計算機科學同樣有它自己的基本問題：什麼是算法?什麼是能計算的?什麼是不能計算的?什麼時候可以認為一個算法是實際可行的?60多年來(甚至從電子計算機出現之前就開始了)計算機科學家一直在考慮這些問題並且給出充滿智慧的回答，這一切對計算機科學產生了深刻的影響。

本書的目的是介紹滲透在計算機科學中的這些基本思想、模型和結果，它們都是該領域的基本範例，它們有很多理由是值得學習的。首先，現代計算機科學中的很多東西直接或間接地以它們為基礎——而其餘的應該……。其次，這些思想和模型是漂亮、有力的，是數學建模的傑出例子，是有長久價值的。此外，它們更是歷史的一部分，是我們這個領域的“共同潛意識”。不首先了解它們，是很難理解計算機科學的。

這些思想和模型在本質上是數學的，這大概不會讓人感到奇怪。雖然計算機肯定是一個物理實體，但是同樣肯定的是關於它的物理方面，如它的分子和它的形狀，能夠值得說的很少；對計算機最有用的抽象顯然是數學的，論證這些抽象所必需的手段也一定同樣是數學的。此外，實際的計算工作需要只有數學才能提供的鐵的保證(希望我們的編譯程式正確地翻譯，應用程式最終停機，等等)。但是，在計算理論中使用的數學與其他套用學科中使用的數學有很大的區別，它一般是離散的，在這裡不強調實數和連續變數，而強調有窮集合和序列。它以很少幾個基本的概念為基礎，通過小心、耐心、仔細、一層一層地處理這些概念，勾畫出它的能力和深奧之處——這很像計算機，在第1章將使你回想這些基本的概念和方法(其中有集合、關係和歸納法)，介紹在計算理論中使用它們的風格。

第2章和第3章描述某些受限制的計算模型。它們能夠完成一些非常特殊的字元串處理工作，例如回答一個給定的字元串是否出現在給定的正文中，如字punk是否出現在莎士比亞文集中，或者檢查一個給定的括弧字元串是否正好平衡——像()和(())()，而不是)()的樣子。這些受限制的計算模型(分別叫做有窮自動機和下推自動機)竟然作為像電路和編譯程式之類很普通的系統的非常有用和高度完善的部分出現在現實生活中。在這裡它們為我們探索算法的一般的形式定義提供極好的熱身練習。此外，看到由於增加或刪除各種特性這些裝置的能力如何增強和減弱(或者，更經常地是，保持不變)是有教益的。其中最值得注意的特性是非確定性，計算的這個迷惑人的特性既是重要的，又是(相當荒謬地)非現實的。

在第4章，我們研究算法的一般模型，其中最基本的模型是Turing機以卓越的英國數學家和哲學家Alan M.Turing (1912—1954)的名字命名。他在1936年發表的開創性的論文標誌計算理論的誕生。Turing也是人工智慧和計算機下棋以及生物學中形態形成領域中的先驅者。在第二次世界大戰中，他幫助破譯德國海軍密碼Enigma。想更多地了解他迷人的一生(以及他最後悲慘地死在官方殘忍和偏執的手中)請閱讀《Alan Turing: The Enigma》，Andrew Hodges 著，New York: Simon Schuster,1983年。。Turing機是第2章和第3章中字元串處理裝置的相當簡單的推廣，結果令人吃驚地成為描述任意算法的一般框架。為了證明這一點，即通常所說的ChurchTuring論題，我們引入越來越複雜的計算模型(Turing機更強的變種，還有隨機存取Turing機和遞歸定義的數值函式)，並且證明它們在能力上全都完全等價於基本的Turing機模型。

再下一章處理不可判定性。某些自然的明確的計算任務具有這種出人意料的性質，可以證明它們超出了算法能夠解決的範圍。例如，問你是否能用給定的若干種形狀的磚鋪整個平面。如果這些形狀中包括一個正方形，或者甚至一個三角形，則答案顯然是“能夠”。但是，如果是幾種稀奇古怪的形狀，或者規定幾種形狀必須至少使用一次，那會怎樣?這肯定是很複雜的問題，你想用機器給出回答。在第5章我們使用Turing機的形式表示證明這個問題和許多其他問題是根本不可能用計算機解決的。

即使當一項計算任務能夠用某個算法解決的時候，也可能不存在解決它的適當快的、實際可行的算法。在本書的最後兩章，我們說明怎么用它們的複雜性對現實生活中的計算問題進行分類：某些問題能夠在合理的，即多項式的時間界限內解決，而另一些問題似乎需要以天文速度，即指數地增長的時間。在第7章我們定義一個叫做NP完全的問題類，它們是一些普通的、實際的、但難得出名的問題(旅行商問題僅是它們中的一個)。我們證明所有這些問題在下述意義下是等價的：如果它們中的一個有有效的算法，則它們每一個都有有效的算法。普遍地相信所有NP完全問題具有固有的指數複雜度；這個猜想是否實際上為真是著名的P≠NP問題，它是當代數學家和計算機科學家面臨的最重要和最深刻的問題之一。

本書有很多篇幅是有關算法及其形式基礎的。然而，大概你也意識到了，在今天的計算機科學教學計畫中，算法課程，包括算法的分析和設計，相當地脫離計算理論的課程。在本書的現行版本中，我們試圖恢復這門課程的某種統一性。結果是，本書對算法也提供了相當不錯的介紹，只是有些專門和非傳統。在第1章形式地介紹算法及其分析，並且在第2章和第3章研究受限制的計算模型和由它們產生的自然的計算問題的時候一再重新提起。這樣一來，在後面探索算法的一般模型的時候，讀者處在較好的位置，能正確評價這種探索的目標並且斷定是能成功的。在講解複雜性時算法同樣擔任主角。因為鑑別複雜問題的最好方法是把它與另一個經得起有效算法考驗的問題進行比較。最後一章用一節敘述對付NP完全性作為結束，給出在遇到NP完全問題時已經成功地使用過的算法技術(近似算法、窮舉算法、啟發式局部搜尋等)。

計算是必不可少的、有力的、優美的、具有挑戰性和不斷發展的——它的理論也是如此。本書僅講了一個激動人心的故事的開頭，它是對從計算理論寶庫中精選出的少量基本論題的樸素介紹。我們希望它將激發讀者去作進一步的探索，每一章最後的參考文獻指出了好的出發點。

圖書目錄

第一版序言(Ⅴ)

第二版序言(Ⅶ)

導言(Ⅸ)

第1章集合、關係和語言(1)

11集合(1)

12關係與函式(4)

13特殊類型的二元關係(7)

14有窮集合與無窮集合(11)

15三個基本的證明技術(13)

16閉包與算法(17)

17字母表與語言(25)

18語言的有窮表示(29)

參考文獻(33)

第2章有窮自動機(34)

21確定型有窮自動機(34)

22非確定型有窮自動機(39)

23有窮自動機與正則表達式(47)

24正則語言與非正則語言(54)

25狀態最小化(58)

26關於有窮自動機的算法(65)

參考文獻(70)

第3章上下文無關語言(72)

31上下文無關文法(72)

32語法分析樹(79)

33下推自動機(83)

34下推自動機與上下文無關文法(87)

35上下文無關語言與非上下文無關語言(92)

36關於上下文無關文法的算法(97)

37確定性與語法分析(102)

參考文獻(115)

第4章Turing機(117)

41Turing機的定義(117)

42用Turing機計算(125)

43Turing機的擴充(130)

44隨機存取Turing機(136)

45非確定型Turing機(144)

46文法(148)

47數值函式(151)

參考文獻(158)

第5章不可判定性(160)

51ChurchTuring論題(160)

52通用Turing機(161)

53停機問題(163)

54與Turing機有關的不可判定問題(166)

55與文法有關的不可解問題(168)

56不可解的鋪磚問題(172)

57遞歸語言的性質(174)

參考文獻(178)

第6章計算複雜性(179)

61P類(179)

62若干問題(181)

63布爾可滿足性(187)

64NP類(190)

參考文獻(194)

第7章NP完全性(196)

71多項式時間歸約(196)

72Cook定理(202)

73其他的NP完全問題(207)

74對付NP完全性(218)

參考文獻(229)

中英對照名詞索引(231)