チューリングマシンとは - IT用語辞典

概要 チューリングマシン（Turing machine）とは、1936年にイギリスの数学者アラン・チューリング（Alan M. Turing）が考案した、計算を行う自動機械の数学的なモデル。形式的な記号操作の組み合わせ、繰り返しで構成されるすべての計算を実行することができる、最も単純化されたコンピュータのモデルとして知られる。 チューリングマシンはマス目に分かれた任意の長さのテープと、テープの上を一マスずつ前後に移動でき、現在位置のマス目の記号を読み取ったり書き込んだりできるヘッドで構成される。 ヘッドは「状態」（内部に記憶された値）を一つ持つことができ、読み込んだ記号と現在の状態の組み合わせによって次の行動を決定する（ヘッドの制御部を独立した要素とみなす場合もある）。ヘッドの行動は3種類あり「テープ上でどちらかの方向に一マス移動する」「現在のマスに記号を書き込む」「内部の状態を変更する」

[pipehead]

Turing machine