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

概要

チューリングマシン（Turing machine）とは、1936年にイギリスの数学者アラン・チューリング(Alan M. Turing)が考案した、計算を行う自動機械の数学的なモデル。形式的な記号操作の組み合わせ、繰り返しで構成されるすべての計算を実行することができる、最も単純化されたコンピュータのモデルとして知られる。

チューリングマシンはマス目に分かれた任意の長さのテープと、テープの上を一マスずつ前後に移動でき、現在位置のマス目の記号を読み取ったり書き込んだりできるヘッドで構成される。

ヘッドは「状態」（内部に記憶された値）を一つ持つことができ、読み込んだ記号と現在の状態の組み合わせによって次の行動を決定する（ヘッドの制御部を独立した要素とみなす場合もある）。ヘッドの行動は3種類あり「テープ上でどちらかの方向に一マス移動する」「現在のマスに記号を書き込む」「内部の状態を変更する」のいずれかを行う。

この機械に外部から、有限個の記号の定義、あらかじめ記号の列が書き込まれたテープ、ヘッドの状態を遷移させる規則の集合（ある「記号-状態」の組み合わせの時にどのような動作を行うかを列挙した表）を与えると、規則に従って次々にヘッドが動作する。

状態遷移表で終了と定義された状態にたどり着くと計算は終了し、その時テープに記載された記号列が計算結果となる。これらは現実のコンピュータにおけるソフトウェア（数学的にはアルゴリズム）に相当する。