Automata and Computability（オートマトンと計算可能性）

引用

Kozen, D. C. (1997). Automata and Computability. Springer.

章の要約

本書は、それぞれ3～10ページの短い50の章からなり、400ページの本のうち3ページから298ページまでを占める。Springer は、学部生向けに計算可能性の基本的な理論モデルを紹介する本と説明しており、構成は3つの流れである。まず有限オートマトン、次にプッシュダウンオートマトンと文脈自由言語、そしてチューリング機械で、有効な計算可能性、決定可能性、ゲーデルの不完全性定理で終わる。出版社はさらに、いくつかの補足的な章がより進んだ概念を紹介し、易しいものから難しいものまで豊富な演習が用意されていると述べている。Springer の章の一覧は、どの章が補足であるかを示していない。

第1～6章：講義の道筋と歴史的展望、文字列と集合、有限オートマトンと正則集合、正則集合についてさらに、非決定性有限オートマトン、部分集合構成法

道筋と歴史的展望を述べる導入、文字列と集合の記法の章、そして決定性・非決定性有限オートマトンに関する4章で、部分集合構成法で終わる。

第7～10章：パターン照合、パターン照合と正規表現、正規表現と有限オートマトン、クリーネ代数と正規表現

パターン照合から正規表現へ進み、有限オートマトンとの同値性、そして代数的な扱いであるクリーネ代数に至る。

第11～13章：準同型、有限オートマトンの限界、ポンピング補題の使い方

準同型に関する閉包性、続いて有限オートマトンにできないことと、ポンピング補題の適用方法を扱う。

第14～17章：DFAの状態最小化、最小化アルゴリズム、マイヒル・ネローデ関係、マイヒル・ネローデの定理

決定性オートマトンの最小化を、まず概念として、次にアルゴリズムとして扱い、続いてマイヒル・ネローデ関係とその定理を述べる。

第18～22章：非決定性オートマトンの縮約、項上のオートマトン、項オートマトンのマイヒル・ネローデの定理、双方向有限オートマトン、2DFAと正則集合

正則言語の理論の拡張。非決定性オートマトンの縮約、独自のマイヒル・ネローデの定理を持つ項上のオートマトン、そして双方向オートマトンである。

第23～26章：文脈自由文法と言語、括弧の釣り合い、標準形、文脈自由言語のポンピング補題

文脈自由言語の部分は、文法に始まり、括弧の釣り合いの章、標準形、そして文脈自由言語のポンピング補題と続く。

第27～31章：プッシュダウンオートマトン、最終状態と空スタック、PDAとCFG、NPDAのCFGによる模倣、決定性プッシュダウンオートマトン

プッシュダウンオートマトン、2つの受理条件、文脈自由文法との同値性、そして決定性プッシュダウンオートマトンを扱う。

第32～35章：構文解析、コッケ・カサミ・ヤンガーのアルゴリズム、チョムスキー・シュッツェンベルジェの定理、パリクの定理

文脈自由言語のアルゴリズムと構造的な定理。構文解析、CKYアルゴリズム、チョムスキー・シュッツェンベルジェの定理、パリクの定理である。

第36～40章：チューリング機械と有効な計算可能性、チューリング機械についてさらに、同等なモデル、万能機械と対角化、決定可能な問題と決定不能な問題

有効な計算可能性のモデルとしてのチューリング機械、同等なモデル、万能機械と対角化、そして最初の決定可能・決定不能な問題を扱う。

第41～43章：帰着、ライスの定理、文脈自由言語に関する決定不能な問題

決定不能性を示す道具としての帰着、続いてライスの定理、そして文脈自由言語に関する決定不能な問いを扱う。

第44～46章：その他の形式化、ラムダ計算、While プログラム

計算のほかの形式化として、ラムダ計算と while プログラムを扱う。

第47～50章：決定不能性の彼方、ゲーデルの不完全性定理、不完全性定理の証明、ゲーデルの証明

最後に、決定不能性の先にあるものと、ゲーデルの不完全性定理とその証明を扱う3章が置かれている。

主要概念

第1～22章：正則言語

• 非決定性と部分集合構成法：非決定性オートマトンを決定性のものに変換する方法。
• 正規表現とクリーネ代数：正則集合の同値な記述。
• ポンピング補題とマイヒル・ネローデの定理：言語が正則であること、または正則でないことを証明する道具。
• DFAの最小化：最小の決定性オートマトンを求めること。

第23～35章：文脈自由言語

• 文脈自由文法、標準形、文脈自由言語のポンピング補題。
• プッシュダウンオートマトン（非決定性と決定性）。
• 構文解析とコッケ・カサミ・ヤンガーのアルゴリズム。

第36～50章：計算可能性

• チューリング機械、万能機械、対角化。
• 帰着とライスの定理：決定不能性を示す方法。
• ラムダ計算と while プログラム：計算可能性のほかの形式化。
• ゲーデルの不完全性定理。

批判的分析

長所

• 短い章。 3～10ページの50章は、それぞれ一度に読み通せるので、課題として割り当てたり、1章ずつ学んだりしやすい。
• ほどよい歩みの最初の講義。 出版社は、初等的な離散数学の経験がある学生向けの、ほどよい歩みの最初の講義として本書を位置づけ、易しいものから難しいものまで豊富な演習があるとしている。
• 通常の中核を超える広がり。 正則言語、文脈自由言語、チューリング機械のほかに、章の一覧にはクリーネ代数、項オートマトン、双方向オートマトン、パリクの定理、ラムダ計算、while プログラム、ゲーデルの定理が含まれ、力のある学生に選択肢を与える。
• 完結した流れ。 有限オートマトンからプッシュダウンオートマトンを経て、チューリング機械と不完全性定理へ進む筋道が、章の順序から見て取れる。

短所

• 計算複雑性理論がない。 章の一覧には、時間・空間計算量やNP完全性の章がなく、本書は計算可能性で終わる。複雑性が必要な講義には、別の教科書が要る。
• 補足の章が示されていない。 出版社は一部の章が補足であると述べているが、章の一覧はそれを区別していないので、読者は自分で読む道筋を選ぶ必要がある。
• 理論中心。 題から応用の色合いが分かるのはパターン照合と構文解析だけで、応用を求める読者は、本書にはほとんど見つからないだろう。

コースにおける位置づけ

Kozen の本は、計算理論のコンパクトな最初の講義である。このコースの本のうち、Sipser の Introduction to the Theory of Computation は、複雑性にまで進む明快な上級入門書で、Kozen が省く部分を補う自然な一冊である。Hopcroft、Motwani、Ullman の Introduction to Automata Theory, Languages, and Computation は、難解性も扱う、より大きな古典的教科書である。Linz と Rodger の An Introduction to Formal Languages and Automata は、説明と具体例を重んじ、Kozen より多くの説明を求める読者のための選択肢になる。MacCormick の What Can Be Computed? は理論を Python のプログラムに結びつけ、コードから入りたい読者に向く。

Arora と Barak の Computational Complexity は複雑性の側を扱う大学院の教科書で、Kozen の計算可能性の内容に続く自然な次の一冊である。

本書の使い方

Springer は、初等的な離散数学の経験がある学生にとって、ほどよい歩みの最初の講義になると述べている。したがって、集合、関係、帰納法による証明に慣れていることが妥当な前提である。

実践的な進め方：

• 中核の道筋： 有限オートマトンと正規表現に第1～6章と第9章、ポンピング補題に第12～13章、文脈自由言語とプッシュダウンオートマトンに第23章、第25章、第27～29章、チューリング機械、帰着、ライスの定理に第36～42章。
• 選択： クリーネ代数（第10章）、DFAの最小化とマイヒル・ネローデ（第14～17章）、構文解析（第32～33章）、その他の形式化とゲーデルの最終章（第44～50章）を、関心に応じて。
• 発展： 項オートマトン、双方向オートマトン、チョムスキー・シュッツェンベルジェの定理とパリクの定理。

演習は読み進めながら解くこと。出版社は、易しいものから難しいものまで豊富に用意されていると強調している。講義がNP完全性まで進むなら、Sipser のような複雑性の教科書と組み合わせる。