計算理論とオートマトン言語理論[第 2 版]

初学者でも読み進められるように証明を含め丁寧に記述し, 全面的に見直しを行った著者渾身の改訂版.“なるほど, そういうことか”を繰り返し体験して楽しみながら学ぶことができる.章末問題にはすべて解答をつけた.
第 I 部: 計算理論とは / すべては計算から始まる / 計算理論のための概念や用語 / 第 II 部: 有限オートマトン, プッシュダウンオートマトン, そして文脈自由文法 / 有限オートマトン / 文脈自由文法 / プッシュダウンオートマトン / 第 III 部: 計算可能性 / チューリング機械 / チューリング機械の万能性とその限界 / 第 IV 部: 計算の複雑さ / クラス P とクラス NP / 論理回路に基づいた計算時間限定の計算 / NP 完全性

『計算理論とオートマトン言語理論[第 2 版]』 (丸岡 章 著、サイエンス社、2021 年 11 月刊) は、有限オートマトンからチューリング機械、NP 完全性までを証明つきで扱う計算理論の教科書です。サイエンス社の「Information & Computing」シリーズの 1 冊で、シリーズ番号は 122、副題は「コンピュータの原理を明かす」です。版元の案内には「初学者でも読み進められるように証明を含め丁寧に記述し, 全面的に見直しを行った著者渾身の改訂版」とあり、章末問題にはすべて解答が付いています。版元は難易度を入門と示しています。著者の丸岡 章は東北大学名誉教授と版元の案内にあります。

4 部 10 章の構成、計算理論の用語から NP 完全性まで

目次は 4 部 10 章で、後ろに解答、文献、おわりに、索引が続きます。第 I 部「計算理論とは」は第 1 章「すべては計算から始まる」と第 2 章「計算理論のための概念や用語」で、第 2 章は集合、系列と言語、関数と問題、グラフ、論理演算とド・モルガンの法則、定理と証明、再帰、アルゴリズムの記述を節に立てています。第 II 部「有限オートマトン, プッシュダウンオートマトン, そして文脈自由文法」は第 3 章「有限オートマトン」、第 4 章「文脈自由文法」、第 5 章「プッシュダウンオートマトン」の 3 章です。第 III 部「計算可能性」は第 6 章「チューリング機械」と第 7 章「チューリング機械の万能性とその限界」、第 IV 部「計算の複雑さ」は第 8 章「クラス P とクラス NP」、第 9 章「論理回路に基づいた計算時間限定の計算」、第 10 章「NP 完全性」です。各章の末尾に問題が置かれています。

有限オートマトンからチューリング機械へ、計算の模型を広げる

有限オートマトンは、有限個の状態と入力に応じた状態の移り変わりだけで文字列を受理するか決める計算の模型です。有限オートマトンが受理する言語の集まりは、正規表現 で書き表せる言語の集まりと一致します。第 3 章は非決定性有限オートマトンと決定性有限オートマトンの等価性、正規表現、受理能力の限界を節に立てています。有限オートマトンにスタックを 1 本加えたものがプッシュダウンオートマトンで、受理できる言語は文脈自由文法が生成する言語と一致します。第 5 章の節はこの等価性を扱い、第 4 章はチョムスキーの標準形と文脈自由文法の言語生成能力の限界を扱います。さらに読み書きのできる無限のテープを持たせたチューリング機械は、手順として書ける計算をすべて表せる模型と考えられています。この考えがチャーチ・チューリングの提唱で、第 6 章の節の題にもなっています。どんなプログラムについても止まるかどうかを判定する アルゴリズム は存在しないことが知られており、これを停止問題の決定不能性と呼びます。第 7 章は万能チューリング機械、停止問題の決定不能性、帰着、ポストの対応問題の 4 節です。

クラス P と NP、計算時間の評価から NP 完全性の証明へ

計算できる問題の中にも、入力の大きさに対して計算時間が爆発的に増える問題があります。クラス P は決定性チューリング機械が入力の長さの多項式の時間で解ける問題の集まりで、クラス NP は非決定性チューリング機械が多項式の時間で解ける問題、言い換えると解の候補が正しいかを多項式の時間で確かめられる問題の集まりです。P と NP が等しいかどうかは未解決の問題として知られています。第 8 章は現実的に計算できる問題とできない問題の例から入り、時間を限定した計算、クラス P とクラス NP、クラス EXP、アルゴリズムの計算時間の評価を節に立てています。アルゴリズムの計算時間を入力の大きさに対する増え方で表す記法が 計算量 の O 記法です。論理式の充足可能性問題が NP 完全であるというクックの定理は、非決定性チューリング機械の計算を論理式で書き表して証明されます。第 9 章は非決定性チューリング機械の論理式による模倣のあらましに始まり、論理回路と離散回路、決定性と非決定性のチューリング機械を模倣する論理回路、論理回路を模倣する論理式を節に立てています。第 10 章は NP 完全の定義とさまざまな NP 完全問題を扱います。

本書は計算理論の用語の整理からオートマトンと形式文法、計算可能性、計算の複雑さまでを 4 部 10 章に収め、章末問題のすべてに解答を付けています。