やさしい計算理論

『やさしい計算理論』 (丸岡 章 著、サイエンス社、2017 年 12 月刊) は、計算理論を基礎から講義の形でまとめた入門の教科書です。版元の書籍ページの見出しには「有限オートマトンからチューリング機械まで」が添えられており、サイエンス社の Information & Computing シリーズの 117 巻にあたります。版元の内容紹介は、計算理論の主要な成果を盛り込み、「証明も含めて初学者が読み進められることを目指した」と説明し、数多くの問題で計算理論を使いこなせるよう工夫したとしています。版元はこの本の難易度を入門に分類しており、著者の丸岡 章は東北大学名誉教授です。

4 部 27 講の構成、系列の操作からポストの対応問題まで

目次は I から IV までの 4 つの部と全 27 講で、各講の末尾に問題が付き、巻末に解答、文献、謝辞、索引が続きます。I「計算理論とは」は 1 講「系列を操作するしくみ」から始まり、計算理論の誕生と計算モデルの考え方、再帰、集合や言語、グラフ、論理演算と証明、アルゴリズムの記述といった準備を 4 講「数学的準備」までで整えます。II「有限オートマトンと正規表現」は 5 講から 13 講で、有限オートマトンの動きと設計、形式的定義、非決定性有限オートマトンとの等価性、正規表現との等価性、受理能力の限界、正規言語のクラスの閉包性を扱います。III「プッシュダウンオートマトンと文脈自由言語」は 14 講から 21 講で、文脈自由文法の定義からチョムスキーの階層、チョムスキーの標準形を経て、プッシュダウンオートマトンと文脈自由文法の相互のシミュレーションまでを置きます。IV「計算可能性」は 22 講のチューリング機械の定義とチャーチ・チューリングの提唱に始まり、多テープチューリング機械、万能チューリング機械、26 講「チューリング機械の停止問題」を経て、27 講「ポストの対応問題の決定不能性」で終わります。

状態の数からテープへ、計算モデルの能力の段差

計算理論は 計算機科学 の基礎科目の 1 つで、計算を行う機械を数学のモデルとして定め、そのモデルで解ける問題と解けない問題の境界を調べます。有限オートマトンは有限個の状態と、入力の記号による遷移だけを持つモデルで、ソフトウェアの設計で使う ステートマシン と同じ考え方に立っています。有限オートマトンが受理できる言語は正規表現で表せる言語と一致することが知られており、grep やエディターの検索で使う 正規表現 の理論は、この結果に基づいています。ただし実務の正規表現エンジンには後方参照のように正規言語の範囲を超える拡張もあります。括弧の対応のような入れ子の構造は有限個の状態では数えきれず、スタックを加えたプッシュダウンオートマトンと文脈自由文法が必要になります。プログラミング言語の構文は、多くが文脈自由文法で書かれます。さらにテープを読み書きできるチューリング機械まで能力を上げると、通常のコンピューターで書けるプログラムの計算はすべて表せると考えられていますが、その上でも、任意のプログラムが停止するかどうかを判定する一般的な手順は存在しません。

4 講「数学的準備」の中身

各講は形式的定義と証明を含みます。4 講「数学的準備」は、集合、系列と言語、関数と問題、グラフ、論理演算とド・モルガンの法則、定理と証明を扱います。目次は IV「計算可能性」の 27 講で終わります。

本書は、系列を操作するしくみと数学的準備から、有限オートマトンと正規表現、文脈自由言語とプッシュダウンオートマトン、チューリング機械と決定不能性までを、4 部 27 講と各講の問題、巻末の解答に収めています。