01 / 導讀
導讀
引用
MacCormick, J. (2018). What Can Be Computed? A Practical Guide to the Theory of Computation. Princeton University Press.
章節概要
全書共十八章：一章導論性概述、討論可計算性理論的第一部（第2–9章）、討論計算複雜度理論的第二部（第10–14章）、討論起源與應用的第三部（第15–17章），以及一章簡短的結語。給教師的序言討論本書適合哪一類理論課程、收錄與捨棄了哪些內容，以及可以圍繞本書設計哪些課程。出版社表示，本書對可計算性與複雜度同等重視，正文使用Python程式（Java版本另於網路提供），並以完全嚴謹的方式陳述與證明標準定理；講義投影片與Python程式可在配套網站取得。各章末尾都有習題。
第1章：Introduction: What Can and Cannot Be Computed?（導論：什麼能計算，什麼不能計算）
把問題分成易解的、難解的與不可計算的三類，更詳細地概述全書，並說明先備知識、學習目標，以及學習計算理論的理由。
第2章：What is a Computer Program?（什麼是電腦程式）
確立第一部通篇使用的模型：「SISO」 Python程式，也就是輸入一個字串、輸出一個字串的程式。本章介紹所需的Python知識、有問題的程式、Python程式的形式定義、判定程式與等價程式，以及真實世界的程式與這個模型的關係。
第3章：Some Impossible Python Programs（幾個不可能存在的Python程式）
對分析其他程式的程式（yesOnString.py、yesOnSelf.py、notYesOnSelf.py）運用反證法，說明某些程式不可能存在，並由此得出結論：完美的除錯程式不可能存在，但有用的除錯程式仍然可以存在。
第4章：What is a Computational Problem?（什麼是計算問題）
介紹圖、字母集、字串與語言，定義計算問題及其類別，並給出「解決」問題，以及辨識與判定語言的形式意義。
第5章：Turing Machines: the Simplest Computers（圖靈機：最簡單的電腦）
定義圖靈機，建構幾部非平凡的圖靈機，從單磁帶過渡到多磁帶圖靈機，再過渡到Python程式；反方向則以Python模擬圖靈機。本章最後指出，古典電腦可以模擬量子電腦，而且所有已知的電腦都是圖靈等價的。
第6章：Universal Computer Programs: Programs That Can Do Anything（通用程式：無所不能的程式）
介紹通用Python程式與通用圖靈機、真實世界中的通用計算、修改其他程式的程式，以及不可判定但可辨識的問題。
第7章：Reductions: How to Prove a Problem is Hard（歸約：如何證明問題很難）
介紹用來證明容易性與困難性的歸約、圖靈歸約的形式定義與性質，並列出一系列不可計算的問題，其中包括與程式無關的問題，最後整理證明不可計算性的技巧。
第8章：Nondeterminism: Magic or Reality?（非確定性：魔法還是現實？）
定義非確定性Python程式與計算樹，證明非確定性不會改變可計算的範圍，給出非確定性圖靈機的形式定義，並討論不可辨識的問題，以及研究非確定性的意義。
第9章：Finite Automata: Computing With Limited Resources（有限自動機：在有限資源下計算）
討論確定性與非確定性有限自動機及其等價性、正規表示式、非正規語言，以及正規語言的組合。
第10章：Complexity Theory: When Efficiency Does Matter（複雜度理論：當效率真的重要時）
介紹漸近執行時間與大O記號、如何判定程式的執行時間、計算模型為何對複雜度有影響，以及複雜度類別。
第11章：Poly and Expo: the Two Most Fundamental Complexity Classes（Poly與Expo：兩個最基本的複雜度類別）
定義Poly與Expo類別，說明它們不受計算模型影響，舉出屬於Expo卻不屬於Poly的問題HALTEX，並討論不合理的輸入編碼。
第12章：PolyCheck and NPoly: Hard Problems That Are Easy to Verify（PolyCheck與NPoly：難解卻容易驗證的問題）
定義多項式時間驗證器與PolyCheck類別，藉由非確定性定義NPoly，證明兩者相同，並論證非確定性似乎確實會改變能有效率計算的範圍。
第13章：Polynomial-time Mapping Reductions: Proving X is as Easy as Y（多項式時間映射歸約：證明X與Y一樣容易）
定義多項式時間映射歸約，以漢米爾頓迴路問題為例說明，並透過歸約把CIRCUITSAT、SAT與3-SAT連結起來。
第14章：NP-Completeness: Most Hard Problems Are Equally Hard（NP完全性：多數難題一樣難）
討論P與NP問題、NP完全性與NP困難性、P = NP會帶來的後果、作為NP中「最難」問題的CIRCUITSAT（庫克–李文定理）、NP完全性的普遍性及其證明技巧。
第15–17章：The Original Turing Machine（最初的圖靈機）；You Can't Prove Everything That's True（並非所有真命題都能證明）；Karp's 21 Problems（卡普的21個問題）
第15章解讀圖靈1936年對「計算機器」的定義，並討論丘奇–圖靈論題。第16章把不可判定性與機械式證明以及哥德爾關於算術不完備性的結果連結起來。第17章逐步梳理卡普關於21個NP完全問題的論文，以及這些問題之間的歸約。
第18章：Conclusion: What Will Be Computed?（結語：什麼將被計算？）
簡短回顧關於「什麼能被計算」的幾個重要概念。
核心概念
第1–4章：程式與問題
- 易解、難解與不可計算的問題：貫穿全書的三種分類。
- SISO Python程式：把一個輸入字串對應到一個輸出字串的程式，是本書主要的計算模型。
- 辨識與判定：接受語言中的字串，與一定會停機並給出正確「是」或「否」之間的差別。
第5–9章：機器、通用性與歸約
- 圖靈等價：圖靈機、Python程式與所有已知電腦能計算的東西都相同的結論。
- 通用程式：能執行以輸入形式給定的任何其他程式的程式。
- 圖靈歸約：藉由說明解決某問題就能解決一個已知不可計算的問題，來證明該問題不可計算。
- 非確定性：分岔成一棵可能性之樹的計算；它不會擴大可計算的範圍。
- 有限自動機與正規表示式：資源有限的計算模型。
第10–14章：複雜度
- Poly與Expo：可在多項式時間與指數時間內解決的問題；這是本書在轉向標準的P與NP之前所用的類別名稱。
- 驗證器與PolyCheck：能快速檢查所提解答的程式，以及具有這種驗證器的問題類別，後者被證明等於NPoly。
- 多項式時間映射歸約：把一個問題有效率地轉換成另一個問題。
- NP完全性與庫克–李文定理：NP中最難的問題，第一個例子是CIRCUITSAT。
第15–18章：起源與應用
- 丘奇–圖靈論題：凡是人依規則能計算的，機器也能計算的主張。
- 不完備性：不可判定性的一個推論，也就是某些為真的算術命題無法被證明。
評析
優點
- 以真實程式為切入點。 出版社的介紹、各章標題，以及The Ubyssey的書評（Angela Tian，2018年8月）都指向同一種設計：不可能性、通用性與歸約先以讀者可以執行的Python程式來論證，之後才給出標準的圖靈機表述。
- 內容均衡。 第一部與第二部給可計算性與複雜度的篇幅大致相當；複雜度部分從Poly與Expo、驗證器與歸約一步步鋪陳，最後才到NP完全性。
- 超出課綱的背景。 第三部解讀圖靈的原始論文，把不可判定性與哥德爾不完備定理連結起來，並梳理卡普的21個問題。
- 配套資源。 講義投影片與程式可在配套網站取得；Ubyssey的書評也提到每章末的習題，以及對每項文獻都附有說明的參考書目。
局限
- 形式語言著墨不多。 有限自動機與正規表示式只占一章，上下文無關文法、下推自動機與喬姆斯基階層都不在各章主題之中。處理這些內容的課程需要另一本教科書。
- Python站在前台。 讀者需要能熟練閱讀Python；Ubyssey的書評也指出，要看懂Python範例需要程式設計經驗。
- 非標準的名稱。 本書先用自己的Poly、Expo、PolyCheck與NPoly等類別展開討論，之後才與P和NP連結，學生需要把這些名稱對應到其他教科書與考試所用的標準記號。
- 複雜度止於NP完全性。 從章名看來，書中沒有處理空間複雜度，也沒有處理隨機化或近似等更深入的主題。
在課程中的定位
在計算理論這門課的書單中，本書是最以程式為中心的入門書。另一本入門教科書 Linz 與 Rodger 的 An Introduction to Formal Languages and Automata 把大部分篇幅用在自動機、文法與下推自動機，並以語法剖析部分作結；MacCormick 則把這些篇幅用在可計算性與複雜度上。以形式語言為主軸的課程，宜以 Linz 與 Rodger 為主要教科書，再用 MacCormick 學習可計算性與NP完全性；以「電腦能做什麼」為主軸的課程，則反過來安排。
Sipser 的 Introduction to the Theory of Computation、Hopcroft、Motwani 與 Ullman 的 Introduction to Automata Theory, Languages, and Computation，以及 Kozen 的 Automata and Computability，以標準的圖靈機記號講授相同的定理，形式語言理論也更多；在讀這些書之前，MacCormick 很適合作為建立直覺的第一輪。Arora 與 Barak 的 Computational Complexity 是研究所教科書，對複雜度的討論遠遠超出第14章。
如何使用本書
出版社表示本書是為初次接觸這個學科的大學部學生而寫，先備要求很少，也適合自學。實際上，修過一門含Python的程式設計入門課，並對反證法有些接觸，前幾章就能讀得很順。
- 核心： 第1章，接著依序讀第一部（第2–8章）與第二部（第10–14章）。兩部前後銜接，尤其非確定性（第8章）是NPoly（第12章）的基礎。
- 第9章： 若課程要考有限自動機就必讀，否則可以略讀。
- 第三部： 選讀的延伸內容；第16章適合對邏輯與數學有興趣的學生，第17章適合想多練習NP完全性的學生。
從配套網站下載程式，邊讀邊執行，尤其是第3、6、7章，那裡的不可能性論證正是由分析其他程式的程式建構而成。在讀某個程式不可能存在的證明之前，先試著修改那個程式。每遇到Poly、Expo、PolyCheck與NPoly，就在旁邊寫下對應的標準名稱，日後轉讀其他教科書時會輕鬆許多。