チューリングマシン | IT用語辞典

チューリングマシン（Turing machine）とは、1936年にイギリスの数学者アラン・チューリング（Alan M. Turing）によって考案された、計算を行う仮想的な自動機械のことである。

チューリング氏は、これを「計算可能性」に関する議論のために提示したとされる。

形式的な記号操作の組み合わせ、反復動作で構成されるあらゆる計算を実行することができる、最も単純化されたコンピュータのモデルと言われている。
 

チューリングマシンは、主にテープとヘッドから構成される機械である。

テープは、マス目に分かれた任意の（無限に長いものであることが想定される）長さのものであり、外部記憶として記号の書き込みが行われる。

ヘッドは、そのテープの上を１マスずつ前後に移動でき、現在位置のマス目の記号を読み取ったり書き込んだりという動作を行う装置である。

ヘッドの動作は3種類ある。

①テープ上で前後どちらかの方向に１マス移動する
②現在のマスに記号を書き込む
③内部の状態を変更する

以上のいずれかの操作を行う。

チューリングマシンは、テープとヘッド、そしてそれらを動かす本体によって構成された機械である。

チューリングマシンのソフトウェアに該当するものとしては、テープに読み書きされる有限個の記号の定義、あらかじめ記号の列が書き込まれたテープ、「状態遷移表」（それぞれの記号と状態の組み合わせの時に、どのような動作を行うかを列挙した表）がある。

これらの規則に従って、ヘッドは自動的に動作し、状態遷移表で終了と定義された状態にたどり着くと計算は終了する。

このときテープに記された記号列が計算結果となる。

この一連の操作の中で「状態遷移表」というものは、「動作の司令を与えている」という役割を果たすことから、数学的に言えばアルゴリズムと同等のものと考えられる。

したがって、このチューリングマシンの動作結果（動作が停止し、結果が得られるか否か）によって、アルゴリズムが存在するか否か（現在、コンピュータでその問題を解くことが可能か否か）を判定することができる。

• チューリングテスト
• オートマトン  （状態機械）
• ステップ数  （プログラムステップ数）
• 磁気テープ  （テープメディア）
• コンピュータ  （電子計算機）
• アキュムレータ  （accumulator）
• Creative Commons  （CC）
• 人工知能  （AI）
• アルゴリズム  （algorithm）
• ループ  （loop）
• 2進数  （binary number）
• プログラム  （program）

「チューリングマシン」を使った例文を以下に記す。