計算理論の基礎：オートマトン
計算理論の基礎を読んでいるので整理のために少しまとめておきます。
計算理論の３大分野
他の分野同様計算の理論もいくつかの分野に分かれていますが、そのなかでも重要なのが以下の３つの分野です。 計算の理論における根本的な疑問は計算機の本質とその能力の限界にあり、各分野別の角度からその答えを探っています。
- 計算の数学的モデル（オートマトン）... 計算の数学的モデルとその性質・能力
- 計算可能性 ... 計算機が解決できる問題とそうでない問題の違い
- 計算の複雑さ ... 問題の難しさを決める要因について
オートマトン
第１巻のテーマはオートマトンです。計算機に対し入力として文字列の集合を与えた時にそのモデルで認識できるかどうかなどが議論の中心になります。本書で紹介されている計算モデルは
の３つです。（チューリング機械は計算可能性への導入として第２巻に収録されています。）
有限オートマトン
はじめに紹介される計算モデルは有限オートマトンと呼ばれるものです。ここで有限なものは記憶領域であり、この制約のためこのモデルの能力は他のモデルに対し限られています。 有限オートマトンの正式な定義は以下の５つの値の組で表されます。
- 状態の集合
- 入力アルファベットの集合
- 遷移関数
- 開始状態
- 受理状態の集合
入力された文字列が受理状態で終了するときこれを"認識する"と言います。またある有限オートマトンで認識される文字列の集合（＝言語）を正規言語と呼びます。つまりある有限オートマトンに対応する正規言語が１つ存在します。
この文字列の集合である言語に対して３種類の演算（和集合演算、連結演算、スター演算）を定義することができ、その総称を正規演算と呼びます。そしてこの正規演算を使って正規言語を表現したものを正規表現と呼びます。
決定性と非決定性
先の定義で表される有限オートマトンというのは決定性という性質を持ちます。非決定性の方が捉えやすいでしょう。ある入力に対して遷移先状態が複数存在し、枝分かれが起きるときこれを非決定的と言います。逆にどの入力アルファベットに対しても遷移関数が１つの状態を出力するとき決定性を持ちます。この２つを区別し決定性有限オートマトン（DFA: Deterministic Finite Automata）と非決定性有限オートマトン（NFA: Nondeterministic Finite Automata）という名前がつけられています。また正規演算を使って簡潔化したNFAを一般化非決定性有限オートマトン（GNFA: Generaristic Nondeterministic Finite Automata）と言います。
直感的には非決定性有限オートマトンの方が表現力があるように感じます。しかし驚くべきことにこのDFAとNFAは能力の点において等価です。本書にはこの証明が記載されているので興味がある人は読んでみてください。このためDFAを使うかNFAを使うかはケースバイケースで使いやすい方を選ぶことになります。本書では正規演算の閉包性を証明するためにNFAが紹介されました。
ある言語に対応する有限オートマトンが存在するかどうか、つまり有限オートマトンの能力の限界、ある言語が有限オートマトンで認識可能かどうかはポンピング補題と呼ばれる定理を用いて背理法により確認することができます。
プッシュダウン・オートマトン
次に紹介されるのはさらに強力な言語を記述できる文脈自由文法（CFG: Context Free Grammer）とそれを認識する計算モデルであるプッシュダウン・オートマトン（PDA: Push-Down Automata）です。この文脈自由文法では正規表現で表すことのできなかった再帰的な構造も扱うことができ、プログラミング言語の仕様やコンパイラといった応用例があります。この文脈自由文法を用いて記述された言語を文脈自由言語（CFL: Context Free Language）と呼びます。
文脈自由文法は以下の４つの値の組で定義されます。
- 変数の集合
- 終端記号
- 変数 → 変数および終端記号、で構成される書き換え規則（rule）の集合
- 開始変数
この文脈自由文法を設計する際のポイントは以下の４つです。
１つの言語に対して様々に書き換え規則を表現することができますが、その中でも最も単純化された表現をChomski標準形と呼びます。
さて先ほどの有限オートマトンは記憶領域に制限がありましたが、この制限を取り除き無限の記憶領域を与えます。ただし今回はそのアクセス方法に制限があり、スタック（First In First Outのデータ構造）としてしか使用できないとします。この計算モデルをプッシュダウン・オートマトンと呼びます。PDAの定義は以下の６つの値の組で表されます。
- 状態の集合
- 入力アルファベットの集合
- スタック・アルファベットの集合
- 遷移関数
- 開始状態
- 受理状態の集合
遷移関数は状態の集合を返すため非決定性を持ちます。先に書いたとおりこのPDAにより認識される言語を文脈自由言語と呼びまたある言語に対しそれを認識するPDAが存在する時その言語を文脈自由言語と呼びます。
有限オートマトンと同様にポンピング補題を使うことによりPDAの限界＝ある言語を認識するPDAが存在するかどうかを証明することができます。
チューリング機械
さてプッシュダウン・オートマトンには記憶領域へのアクセス方法に制限がありました。この制限を取り除き、テープ上に記録したどの領域にも自由にアクセス可能にした計算モデルをチューリング機械と呼びます。チューリング機械の持つ性質として、受理状態あるいは拒否状態に入った時点で停止すること、ループという永久に停止しない状態が存在することがあります。このチューリング機械はコンピュータに対する正確なモデルになっており、チューリング機械の能力の限界を調べることはコンピュータにできないことを知ることに繋がります。定義は以下の７つの値の組で表されます。
- 状態の集合
- 入力アルファベットの集合
- テープ・アルファベットの集合
- 遷移関数
- 開始状態
- 受理状態
- 拒否状態
チューリング認識可能であるとはある言語に対し認識可能（受理・拒否・ループのいずれかの終了状態であることがわかる）なチューリング機械が存在することであり、チューリング判定可能であるとはある言語に対し判定可能（受理・拒否のいずれか）なチューリング機械が存在することを言います。
このチューリング機械にはいくつかの亜種が存在し、テープを２本もつなどそれぞれ変更点がありますが、自由なアクセスが可能な無限の記憶領域という本質は共通しており、一方でもう一方をシミュレート可能なため能力の点では等価です。
ある問題の解を求めるアルゴリズムがそれをチューリング機械上でのステップを示すことと等価であることをChurch–Turing提唱といいます。それによりある問題を解くアルゴリズムが存在するかどうかをチューリング機械の判定可能性により確かめることができます。
まとめ
ざっくりした説明になってしまいました。詳しくは書籍の方をご覧ください。それぞれの数学的証明もじっくり掲載されているので証明から理解したい人にもおすすめです。
