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

