スマートフォン用の表示で見る

チューリングマシン

コンピュータ

チューリングマシン

ちゅーりんぐましん

[英] Turing Machine(TM)

チューリングマシンは、計算模型のひとつで計算機を数学的に議論するための、単純化・理想化された仮想機械である。

1936年イギリス数学者アラン・チューリング論文「計算可能数について──決定問題への応用」で発表された。同様の考え方は同年にエミール・ポスト (Emil Post) も独自に発表している。構想の理由、動機についてはポストの論文が明確だが、仮想機械自体に関する記述はチューリング論文が詳細である。

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

原理

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

D