チューリングマシン

チューリングマシンはすなわち、計算機を数学的に検証、議論する上で必要となる、理想化、単純化された仮想的な計算機である。

この理論では、無限に長いテープと、そのテープに情報を読み書きするヘッドとを持った、いくつかの簡単な基本操作によって動く機械が想定されており、その機械の有限回の操作で数学の形式体系と等価な働きをすることを導いた。

つまりチューリングマシンは、少なくとも次のような装置を持つ。

1. 無限に長いテープ
2. そのテープに情報を読み書きするヘッド
3. 計算機内の状態を保持するメモリー

そして、計算機内の状態と、ヘッドで読み取った情報の組み合わせに応じて、次のいずれかの動作を行なう。

• ヘッドの位置の情報を読み取る
• ヘッドの位置に情報を書き込む
• 計算機内の状態を変更する
• ヘッドを左右のいずれかに一つ分移動する

以上の動作を、計算機内の状態が停止になるまで繰り返して実行する。