チューリングマシン　【Turing machine】

チューリングマシンとは、1936年にイギリスの数学者チューリングが考案した計算を行なう機械のモデル。基本的な構成はマス目で分割された一本のテープと、テープにデータを書き込み・読み出しする一個のヘッドから成っている。

　チューリングマシンはあらかじめ設定された幾つかの「状態」を持っており、その「状態」とヘッドから読み出したデータの組み合わせによって、「ヘッドをテープ上で一マス移動させる」「テープのヘッドのあるマスにデータを書き込む」「『状態』を変更する」のいずれかの動作を行なう。その後、移動後のヘッド位置からデータを読み込み、そのデータと新しい「状態」の組み合わせに従って、次の動作を行なう。

　単純な原理だが、一定の手順に従えば答えが求められるような計算は、理論上すべてチューリングマシンで実行できるとされている。チューリングマシンそのものは理論だけの存在であり、実際に製作されたわけではないが、現在のコンピュータも突き詰めればチューリングマシンの原理に従っていると言える。