チューリングマシンとは

チューリングマシンとは、計算を行うための基本的な機能が定義された、仮想的な装置です。チューリングマシンは、計算可能性の議論を行うため、数学者チューリングにより1936年に考案されました。

チューリングマシンの構造は非常にシンプルで、制御部（以下、ヘッド）と十分な長さを持つ記憶部（以下、テープ）により構成されます。ヘッドは有限個の命令を順番に実行します。

テープはマス目に分かれており、それぞれ記号が設置されています。ここで記号は、ビット（２進数）を表す「１」と「０」の他、テープの左端を表す「＃」、空白を表す「ｂ」などを定義します。

チューリングマシンの動作

チューリングマシンの命令もシンプルで、次の４つで構成されます。

例えば、最初のビットを反転させる命令［I1］は以下のように表されます。ここで、「halt」は処理の終了を表します。

命令	記号の読出し（read）	記号の書込み（write）	ヘッドの移動（move）	次の命令（goto）
［I1］	＃０１ｂ	＃１０ｂ	right right right halt	I1 I1 I1 －

２行目は「０」が読み出された場合は「１」を書込み、３行目は「１」が読み出された場合は「０」を書込むことを表しているため、ビットが反転されることが分かります。また、４行目は空白「ｂ」で動作を止めることが表しています。

ヘッドの開始位置を左端として、この命令を実行させると以下のようになります。初期のテープの状態①を「#1010b1･･･」として、ヘッドの位置をマス目の左側に［I1］として書いています。

以上のように、４ビットの反転をするのに、６ステップの命令を実行していることが分かります。

万能チューリングマシンとは、他のチューリングマシンの動作を模倣する能力を有するチューリングマシンです。

万能チューリングマシン $M_u$ は、整数の組 $i$ と $x$ を入力として、入力 $x$ に対するチューリングマシン $M_i$ の計算を実行します。これを式で表すと以下になります。

$$M_u(i,x)=M_i(x)$$

万能チューリングマシンはテープを２本使用し、１本のテープ（テープA）は $M_i(x)$ の計算を実行するために使用され、もう１本のテープ（テープB）は $M_i$ の命令記述（プログラム）を格納するために使われます。

この場合、実行のステップは以下になります。

命令	記号の読出し（read）	記号の書込み（write）	ヘッドの移動（move）	次の命令（goto）
［I1］	＃０１ｂ	＃１０ｂ	right right right halt	I1 I1 I1 －