機械・算法
計算を行うためのモデルとして，機械の概念が登場する．機械は計算を実行するための抽象的なモデルであり，その具体的な実装は多岐にわたる．
有限オートマトン
有限オートマトン (finite automaton) または 有限状態機械 (finite state machine) とは，有限個の状態と遷移と動作の組み合わせからなる数学的に抽象化された「ふるまいのモデル」である．機械の典型例としては，デジタル回路やプログラムの設計で使われることがあり，ある一連の状態をとったときどのように論理が流れるかを調べることができる．
定義と例
\[M=(Q,\Sigma,\delta,q_0,F)\]タプル (Tuple) における $M$ で，$Q$ は状態の集合，$\Sigma$ は入力アルファベット，$\delta: Q \times\Sigma\to Q$ は状態遷移函数，$q_0\in Q$ は初期状態，$F \subseteq Q$ は受理状態の集合である．有限オートマトン $M$ は，正則言語 (regular language) を受理する能力を持つ．
\(\Sigma=\{\texttt{a},\texttt{b}\}\) 上の文字列が与えられ，その中に連続する $3$ 文字として $\texttt{aba}$ が現れるか否か知りたいとしよう．例えば与えられた文字列が $\texttt{abbaabab}$ であるときは条件を満すと判断（受理）し，$\texttt{abbaabba}$ であるときは満さないと判断（不受理）したい．つまり，正則言語
\[\text{C}{\scriptsize\text{ONTAINS-ABA}}=\{x\in\Sigma^*:xは\texttt{aba}という連続する3文字を含む\}\]に属するか否かを正しく区別したいのである．下図のような仕掛を有限状態機械という．1
有限オートマトンの限界
有限オートマトンは眼前の入力に応じて状態を変えるだけの単純な計算機構であった．入力のうち既に読んだ部分については，それを読んだ結果どの状態に至ったかのみを記憶に留め，経緯は忘れてしまう．前例の $Q$ は，現時点でそれぞれ以下の条件が成立つことを表している．
| 状態 | 意味 |
|---|---|
| $q_0$ | まだ $\texttt{aba}$ は現れておらず，現時点で最後が $\texttt{a}$ でも $\texttt{ab}$ でもない |
| $q_1$ | まだ $\texttt{aba}$ は現れていないが，現時点で最後の数字は $\texttt{a}$ である |
| $q_2$ | まだ $\texttt{aba}$ は現れていないが，現時点で最後の二つの数字は $\texttt{ab}$ である |
| $q_3$ | 既に $\texttt{aba}$ は現れた |
如何に長い文字列を読まされても，この $4$ 通りに分類してさえおけば以後の判断に困らないという．正則言語 $\text{C}{\scriptsize\text{ONTAINS-ABA}}$ の単純さを利用していたといえる．
そのような性質をもたない入力（言語）もあり，有限オートマトンでは認識できない．例えば，\(\Sigma=\{\texttt{a},\texttt{b}\}\) 上，幾つかの連続した $\texttt{a}$ の後に同数の $\texttt{b}$ が続くという形をした文字列の全体，すなわち，文脈自由言語 (context-free language)
\[\text{C}{\scriptsize\text{ONTAINS-ANBN}} =\{x\in\Sigma^*:\exists n\in\mathbb{Z}_{>0}, x=\texttt{a}^n\texttt{b}^n\}\]がそれである．これを認識するには $\texttt{a}$ の個数を完全に数えねばならず，それは幾らでも大きくなりうるので，状態が有限個では無理である．
チューリング機械
理解を容易にするために，ここでは煩雑な チューリング機械 (Turing machine) の厳密な定義に代えて，有限オートマトンと比べて，チューリング機械の設計上の拡張点について述べる．
設計上の拡張
チューリング機械には，テープという $1$ 次元の記憶装置が導入されている．
- 文字列の読み取り順序は，単方向（左から右へのみ）から双方向（左から右へ，または，右から左への両方）に拡張された．
- テープに対する作業は，読み取りのみならず，追加，削除，修正の書き込み作業も含まれる．
- $1$ 回の作業で単方向に $1$ 文字ずつ移動する制限が解除され，テープ上で左右に移動するステップ数を指定し，任意の位置にジャンプして作業を行うことが可能となった．
- $1+k$ 本のテープを使用できる．これには，$1$ 本の読み取り用のテープ（入力テープ）と，$k$ 本の作業テープが含まれ，これにより $k$ 次元の状態遷移函数を実現できる．
例えば，前例の文脈自由言語 \(\text{C}{\scriptsize\text{ONTAINS-ANBN}} =\{\texttt{a}^n\texttt{b}^n:n\in\mathbb{Z}_{>0}\}\) は有限状態機械には認識されなかったが，チューリング機械によって認識される．この機械は作業テープを一本もつが，入力テープ上では常に右へと読み進める．読んだ文字が $\texttt{a}$ ならば作業テープ上に $\texttt{c}$ を書いて右に行く．初めて $\texttt{b}$ を読むと，作業テープ上では左へ戻る．以後は $\texttt{b}$ を見る毎に作業テープの $\texttt{c}$ を一つ消して左へ進む．入力を読み終った次の時刻にちょうど作業テープ上の $\texttt{c}$ を消し終った場合のみ受理する．
チューリング機械の能力
チューリング機械による計算可能性は，任意の文脈自由言語を判定できるだけでなく，チューリングと同時代（$1930$ 年代）にクリーニ (S. Kleene) やチャーチ (A. Church) が考案した 再帰函数 (recursive function) や ラムダ計算 (lambda calculus) など，数や式に対する機械的な処理を捉えた他の概念とも等価であることが知られている．
そればかりか，チューリング機械の能力を超える現実的な計算の仕組は，今日に至るまで見つかっていない．チューリングの論文でも，規則に従って計算をする者が取り得るあらゆる行動がこの機械の動きとして表せそうだという理由が説明されている．およそ明確に記述された処理手順は皆チューリング機械で書ける，というこの主張は チャーチ・チューリングのテーゼ (Church–Turing thesis) と呼ばれている．勿論「明確に記述された手順」が厳密な概念でない以上，この主張は数学的に証明できる類のものではないが，広く受入れられている．
$1970$ 年代には $\mathcal{NP}$ 完全問題という，特定のクラスの問題に対して効率的なアルゴリズムが存在しない可能性が示唆され，計算理論の分野は大きな進展を見せた．
機械 $=$ アルゴリズム
特定の問題を解決するために機械上で実行される一連の 単純な処理 (primitive computational step) 手順を定めたものを算法（アルゴリズム）という．そのため，「機械」と「アルゴリズム」は同質であり，アルゴリズムの設計は，特定の入力に対して効率的に解を提供するための計算機科学の中で非常に重要な要素である．
この内容については，河村彰星先生の「計算量理論 演習問題」を参考した． ↩︎