ユーザ用ツール

サイト用ツール


チューリングマシン

Touring machine

 Touring A.M.によって考案された抽象的計算機械のこと.ある問題を解くアルゴリズムが存在するかというかたちの問題を数学的に厳密に議論するために,アルゴリズムという直観的な概念に対応する数学的な概念として考え出された.最近では,アルゴリズムの効率の研究において,コンピュータの数学的モデルとしても使用される.チューリングマシンMは無限個のマス目に分割され左右両方向にのびているテープ,現在のテープのマス目の位置を見ているヘッド,それらを制御する制御部の三つの部分からなる.テープにはある有限種類の記号がマス目一つに対して一種類記入されている.Mの動作は,上記のテープの記号を入力として,そのときヘッドの見ている記号aと制御部の状態qとの組合せ(a,q)に対応する動作を指定することによって決まる.どのようなアルゴリズムも,このようなチューリングマシンによって原理的には表現が可能であることが,経験的に知られている.しかし,多くの応用において,できるだけ自然なアルゴリズムが望ましいので,そのために表現したいアルゴリズムのタイプに応じてチューリングマシンのいろいろなモデルが考え出されている.