計算理論導論

引用

Sipser, M. (2012). Introduction to the Theory of Computation (3rd ed.). Cengage Learning.

章節概要

全書分為三個部分，依照這門學科的傳統順序展開：自動機與語言、可計算性理論、複雜性理論。最前面是一個預備性的第0章，每章末尾都有習題、問題與解答。作者把本書描述為面向高年級本科生或研究生入門課程的教材，涵蓋自動機理論、可計算性理論和複雜性理論。

第0章：引言

開篇一章彙集全書用到的數學背景，包括集合和圖，並配有編號的例子和問題。書中先給出定義和定理的形式化陳述並加以證明的做法，從這裡開始確立。

第一部分，第1–2章：自動機與語言

第1章「正則語言」引入最簡單的計算模型及其所識別的語言。第2章「脈絡無關語言」進入表達能力更強的下一個層次。第三版在這裡新增一節，討論決定性脈絡無關文法；出版社稱之為首創的理論處理，與語法分析和LR(k)文法相聯絡。

第二部分，第3–6章：可計算性理論

第3章「邱奇–圖靈論題」引入圖靈機，作為演算法能做什麼的標準模型。第4章「可決定性」追問哪些問題根本上能被這類機器解決。第5章「可歸約性」把歸約發展為證明更多問題不可決定的主要工具。第6章「可計算性理論的進階主題」在核心序列之外擴展了更多結果。

第三部分，第7–10章：複雜性理論

第7章「時間複雜性」從「什麼可以計算」轉向「在資源限制內可以計算什麼」。第8章「空間複雜性」對儲存做同樣的討論。第9章「難解性」考察可證明困難的問題，第10章「複雜性理論的進階主題」以更多專題收尾。

核心概念

第一部分：自動機與語言

• 正則語言：由最簡單的計算模型識別的語言，是第1章的主題。
• 脈絡無關語言：下一個語言類別，是第2章的主題；第三版增加了決定性脈絡無關文法。

第二部分：可計算性

• 圖靈機與邱奇–圖靈論題：代表直覺演算法概念的形式模型。
• 可決定性：一個問題能否被演算法解決。
• 可歸約性：透過歸約把不可決定性從一個問題傳遞到另一個問題。

第三部分：複雜性

• 時間與空間複雜性：度量計算所需的資源，是第7、8章的主題。
• 難解性：可證明困難的問題，是第9章的主題。

評析

優點

• 以清晰為主要賣點。 Cengage 稱本書保持平易近人的風格，修訂及時，增加了習題和更令人印象深刻的例子，同時保持嚴謹與形式化。
• 用一條路線貫穿三個主題。 各部分遵循大多數課程講授這些內容的順序：先自動機，再可計算性，最後複雜性。第3–5章的標題顯示，可決定性與可歸約性是在圖靈機的基礎上依次建立的。
• 習題支援。 每章末尾都有習題、問題與解答；第三版增加了新的習題、問題和解答，作者還為該版本維護公開的勘誤表。
• 與語法分析的聯絡。 關於決定性脈絡無關文法的新增一節把理論與LR(k)分析聯絡起來，對在編譯原理課上接觸過文法的讀者很有用。

侷限

• 全書以證明為主。 出版社強調其數學處理「包括高深的定理與證明」，因此缺乏證明經驗的讀者要做好一邊學習內容、一邊學習寫證明的準備。
• 只講理論。 章節目錄中沒有基於程式設計的內容；想透過執行程式來理解可計算性的讀者需要另找資料。
• 高階各章有所取捨。 第6章和第10章是若干後續專題的彙集，並不對其中任何一個做完整展開。

在課程中的定位

在本課程書單中，Sipser 是分量適中、以證明為主的核心教材。Peter Linz 與 Susan Rodger 的 An Introduction to Formal Languages and Automata 更為平緩，重解釋和例題而輕形式化；John MacCormick 的 What Can Be Computed? 在正式論證之前先用簡短的Python程式講解可計算性與複雜性，適合覺得形式化方法抽象的讀者作為第一本書。Dexter Kozen 的 Automata and Computability 以短講的形式組織，含完整證明和大量分級習題；Hopcroft、Motwani 和 Ullman 的 Introduction to Automata Theory, Languages, and Computation 是範圍相近的經典替代品。Arora 與 Barak 的 Computational Complexity 是研究生層次的讀物，從第7–10章停下的地方繼續。

如何使用本書

本書適合已修過離散數學、能讀寫證明的高年級本科生和研究生新生。

建議的學習安排：

• 核心： 先讀第0章瞭解記號（熟悉的話可略讀），然後依次讀第1–5章和第7章。這些構成完整的第一門課：正則語言與脈絡無關語言、圖靈機、可決定性與歸約，以及時間複雜性。
• 接下來： 第8章（空間複雜性）和第9章（難解性）。
• 可選： 若對語法分析感興趣，可讀第2章末尾關於決定性脈絡無關文法的部分；時間更長或研究生層次的課程可加入「進階主題」第6章和第10章。
• 練習： 在看解答之前先做每道習題和問題，並用完整的句子寫出證明；書中的證明就是範例。請對照作者為你手頭版本提供的勘誤表。

如果覺得第1–2章太抽象，可以先讀一本更平緩或基於程式的書，再回到 Sipser 讀第3–5章，那裡開始講可計算性。自學時，可以把第4、5、7章的主要歸約和證明套路記在筆記本上；歸約和證明套路在各章中反覆出現，憑記憶重新推導一遍是檢驗理解程度的快捷方式。