計算理論への入門

引用

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

章の要約

本書は三部構成で、この分野の伝統的な順序、すなわちオートマトンと言語、計算可能性理論、計算量理論に沿って進む。最初に準備的な第0章があり、各章の末尾には演習、問題、解答がある。著者は本書を、オートマトン理論、計算可能性理論、計算量理論を扱う、学部上級または大学院入門レベルの授業のための教科書と説明している。

第0章：序論

冒頭の章では、集合やグラフを含め、全体で使う数学的背景をまとめ、番号付きの例と問題を添えている。定義と定理を形式的に述べて証明するという本書の流儀は、ここで初めて示される。

第I部、第1–2章：オートマトンと言語

第1章「正則言語」では、最も単純な計算モデルと、それが認識する言語を導入する。第2章「文脈自由言語」では、表現力が一段上のクラスに進む。第3版ではここに、決定性文脈自由文法を扱う新しい節が加えられた。出版社はこれを、構文解析やLR(k)文法に結びつく、初めての理論的取り扱いと紹介している。

第II部、第3–6章：計算可能性理論

第3章「チャーチ=チューリングのテーゼ」では、アルゴリズムにできることの標準モデルとしてチューリング機械を導入する。第4章「決定可能性」では、そうした機械によってそもそも解ける問題はどれかを問う。第5章「還元可能性」では、さらに多くの問題が決定不能であることを示す主要な道具として還元を展開する。第6章「計算可能性理論の発展的話題」は、中核の流れを超えるさらなる結果で部を広げる。

第III部、第7–10章：計算量理論

第7章「時間計算量」は、「何が計算できるか」から「資源の制限内で何が計算できるか」へと向きを変える。第8章「空間計算量」は、記憶領域について同様の議論をする。第9章「難解性」は証明可能に難しい問題を調べ、第10章「計算量理論の発展的話題」はさらなる話題で本書を締めくくる。

主要概念

第I部：オートマトンと言語

• 正則言語：最も単純な計算モデルが認識する言語で、第1章の主題。
• 文脈自由言語：次のクラスで第2章の主題。第3版で決定性文脈自由文法が加わった。

第II部：計算可能性

• チューリング機械とチャーチ=チューリングのテーゼ：直観的なアルゴリズムの概念を表す形式モデル。
• 決定可能性：問題がそもそもアルゴリズムで解けるかどうか。
• 還元可能性：還元によって、ある問題から別の問題へ決定不能性を移すこと。

第III部：計算量

• 時間・空間計算量：計算に必要な資源の測定で、第7章と第8章の主題。
• 難解性：証明可能に難しい問題で、第9章の主題。

批判的分析

長所

• 明快さが出版社の主な売り。 Cengageは、本書が親しみやすい文体を保ち、時宜を得た改訂、追加の演習、より記憶に残る例を備えながら、厳密さと形式性を維持していると説明している。
• 三つの主題を一本の道筋で。 各部は多くの授業が教える順序、つまりオートマトン、計算可能性、計算量の順に並ぶ。第3–5章の題名から、決定可能性と還元可能性がチューリング機械の上に順に積み上げられることが分かる。
• 演習の支え。 各章末に演習、問題、解答があり、第3版では新しい演習・問題・解答が追加され、著者はこの版の正誤表を公開している。
• 構文解析との接点。 決定性文脈自由文法の新しい節は、理論を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章が抽象的に感じられる場合は、より穏やかな本かプログラムを使う本から始め、計算可能性が導入される第3–5章で Sipser に戻ってもよい。独習では、第4・5・7章の主要な還元と証明の型をノートにまとめておくとよい。還元と証明の型は章ごとに繰り返し現れ、記憶だけで再導出してみることが理解度を手早く確かめる方法になる。