チューリングマシンとは
チューリングマシンとは、計算を行うための基本的な機能が定義された、仮想的な装置です。チューリングマシンは、計算可能性の議論を行うため、数学者チューリングにより1936年に考案されました。
チューリングマシンの構造
チューリングマシンの構造は非常にシンプルで、制御部（以下、ヘッド）と十分な長さを持つ記憶部（以下、テープ）により構成されます。ヘッドは有限個の命令を順番に実行します。
テープはマス目に分かれており、それぞれ記号が設置されています。ここで記号は、ビット（２進数）を表す「１」と「０」の他、テープの左端を表す「＃」、空白を表す「ｂ」などを定義します。
チューリングマシンの動作
チューリングマシンの命令
チューリングマシンの命令もシンプルで、次の４つで構成されます。
- ヘッドの位置にあるマス目の記号を読む（resd）
- ヘッドの位置にあるマス目に記号を書く（write）
- ヘッドの位置を左右どちらかのマス目に移動させる（move）
- 次の新しい命令に進む（goto）
例えば、最初のビットを反転させる命令（I1）は以下のように表されます。ここで、「halt」は処理の終了を表します。
| 命令 | 記号の読出し （read） |
記号の書込み （write） |
ヘッドの移動 （move） |
次の命令 （goto） |
| Ｉ１ | ＃ ０ １ ｂ |
＃ １ ０ ｂ |
right right right halt |
I1 I1 I1 － |
チューリングマシンの実行例
ヘッドの開始位置を左端として、この命令を実行させると以下のようになります。初期のテープの状態を「#1010b1･･･」として、ヘッドの位置をマス目の左側に［I1］として書いています。
| [I1]＃１０１０ｂ１ ＃[I1]１０１０ｂ１ ＃０[I1]０１０ｂ１ ＃０１[I1]１０ｂ１ ＃０１０[I1]０ｂ１ ＃０１０１[I1]ｂ１ ＃０１０１ｂ１ |
以上のように、４ビットの反転をするのに、６ステップの命令を実行していることが分かります。
万能チューリングマシン
万能チューリングマシンとは、他のチューリングマシンの動作を模倣する能力を有するチューリングマシンです。
万能チューリングマシン（$M_u$）は、整数の組 $i$ と $x$ を入力として、入力 $x$ に対するチューリングマシン（$M_i$）の計算を実行します。これを式で表すと以下になります。
$$M_u(i,x)=M_i(x)$$
万能チューリングマシンはテープを２本使用し、１本のテープは $M_i(x)$ の計算を実行するために使用され、もう１本のテープは $M_i$ の命令記述（プログラム）を格納するために使われます。
