チューリングマシン
チューリングマシンとは、アルゴリズムによる計算を数学的に定義するために、アラン･チューリングが考案した抽象計算モデルです。チューリングマシンは、何が計算できるか、どれくらい効率的に計算できるかなどを研究する理論計算機科学の基礎となっています。
構成要素
チューリングマシンの構造は非常にシンプルで、制御部（以下、ヘッド）と十分な長さを持つ記憶部（以下、テープ）により構成されます。テープは理論上無限に長く、計算中に必要なだけ記憶領域を利用できるとされています。
- テープ（Tape）
理論上は左右無限に続く記憶領域で、マス目（セル）に分割されている。各セルには１個の記号（テープアルファベット）が書かれている。 - 読み書きヘッド（Head）
現在位置のセルを読む、記号を書き換える、左(L)、右(R)、停止(S)のいずれかに移動する。 - 有限制御装置（Finite Control）
チューリングマシンの状態（状態集合）を保持する。
形式的定義
チューリングマシンは通常は以下のような変数の組で定義されます。
$$M=(Q,\Sigma,\Gamma,\delta,q_0,q_a,q_r)$$
- $Q$：状態集合 $\{q_0,q_a,q_r,\cdots\}$
$q_0$：初期状態、$q_a$：受理状態（accept）、$q_r$：拒否状態（reject） - $\Gamma$：テープアルファベット
計算中を含めてテープ上に現れる全記号集合 $\{0,1,a,b,\cdots,\Box\}$ - $\Sigma$：入力アルファベット
最初の入力に使う記号集合 - $\delta$：遷移関数
遷移関数
チューリングマシンの動作を表す遷移関数 $\delta$ は以下で定義されます。
$$\delta:Q\times\Gamma\,\to\,Q\times\Gamma\times\{L,R,S\}$$
命令は、現在の状態 $q$ 、読み取った記号 $a$ に応じて、次の状態 $q’$ 、書き込む記号 $b$ 、移動方向 $D$ を定めます。
$$\delta(q,a)=(q’,b,D)$$
動作の流れ
ヘッドは有限個の命令を順番に実行します。テープはマス目に分かれており、それぞれ記号が設置されています。チューリングマシンでは、命令を以下のような任意の有限記号集合を使います。
- 初期状態から開始、ヘッドをテープの先頭に合わせる。
- ヘッドがテープのセルの記号を読む。
- 遷移表（遷移関数）を参照する。
- 遷移表に従って、書き込み → ヘッド移動 → 状態更新を行う。
- 停止状態（受理状態または拒否状態）になるまで繰り返す。
動作例
本記事では説明を簡単にするため、ビット（２進数）を表す「１」と「０」、空白を表す「□」を定義します。
遷移表
チューリングマシンの命令もシンプルで、次の４つで構成されます。
- ヘッドの位置にあるマス目の記号を読む（read）
- ヘッドの位置にあるマス目に記号を書く（write）
- ヘッドの位置を左右どちらかのマス目に移動させる（move）
- 状態を更新する（update）
例えば、最初のビットを反転させる遷移表（命令）は以下のように表されます。ここで、「停止」は処理の終了を表します。
| 状態 | 記号の読出し （read） |
記号の書込み （write） |
ヘッドの移動 （move） |
次の状態 （update） |
| $q_1$ | 0 | 1 | 右 | $q_1$ |
| $q_1$ | 1 | 0 | 右 | $q_1$ |
| $q_1$ | □ | □ | 停止 | － |
１行目は「０」が読み出された場合は「１」を書込み、２行目は「１」が読み出された場合は「０」を書込むことを表しているため、ビットが反転されることが分かります。
また、３行目は入力列の末尾を表す空白記号「□」で、これ以上反転すべきビットが存在せず停止する。
実行例
ヘッドの開始位置を左端として、この命令を実行させると以下のようになります。初期のテープの状態①を「･･･□1010□□･･･」として、初期状態を［$q_1$］としています。
| ① | □［$q_1$］１０１０□□ | 「1」の場合は「0」を書込み、ヘッドを右に移動 →② |
| ② | □０［$q_1$］０１０□□ | 「0」の場合は「1」を書込み、ヘッドを右に移動 →③ |
| ③ | □０１［$q_1$］１０□□ | 「1」の場合は「0」を書込み、ヘッドを右に移動 →⓸ |
| ⓸ | □０１０［$q_1$］０□□ | 「0」の場合は「1」を書込み、ヘッドを右に移動 →⑤ |
| ⑤ | □０１０１［$q_1$］□□ | 「ｂ」の場合は処理を終了 →⑥ |
| ⑥ | □０１０１□□ | 終了状態 |
以上のように、４ビットの反転をするのに、６ステップの命令を実行していることが分かります。
万能チューリングマシン
万能チューリングマシン（Universal Turing Machine）とは、他のチューリングマシンの動作を模倣する能力を有するチューリングマシンです。
万能チューリングマシン $M_u$ は、整数の組 $i$ と $x$ を入力として、入力 $x$ に対するチューリングマシン $M_i$ の計算を実行します。これを式で表すと以下になります。
$$M_u(i,x)=M_i(x)$$
- $M_i$：$i$ 番目のチューリングマシン
- $x$：入力データ
- $M_u$：万能チューリングマシン
万能チューリングマシンは、マシン番号 $i$ と入力 $x$ を受け取ると、あたかもマシン $M_i$ を実行したかのような結果を返します。
構成要素
万能チューリングマシンはテープを２本使用し、１本のテープ（テープA）は $M_i(x)$ の計算を実行するために使用され、もう１本のテープ（テープB）は $M_i$ の命令記述（プログラム）を格納するために使われます。
動作の流れ
実行のステップは以下になります。
- テープAより $i$ を読み出す。
- テープBに命令 $M_i$ を書き込む。
- テープAに入力データ $x$ をコピーする。
- テープAに対し $M_i(x)$ を実行する。
現代コンピュータとの関係
万能チューリングマシンは、他の任意のチューリングマシンのプログラムと入力を与えると、その動作を模倣できるチューリングマシンです。
現代のコンピュータも同様に、ハードウェア自体を作り替えるのではなく、メモリに格納されたプログラムを読み込んで様々な処理を実行します。この考え方は、プログラム内蔵方式（ストアドプログラム方式）と呼ばれます。
従って、万能チューリングマシンは、プログラムをデータとして扱える汎用計算機の理論モデルであり、現代コンピュータの原理的な先駆けであると言うことができます。
