チューリングマシン
ここでは非形式的(直感的)に述べる。理論的には形式的に述べる必要がある。
チューリングマシンには、いわゆるハードウェアに相当するものとして、
その表面に記号を読み書きできるテープ。長さは無制限(必要になれば順番にいくらでも先にシークできる)とする
テープに記号を読み書きするヘッド
ヘッドによる読み書きと、テープの左右へのシークを制御する機能を持つ、有限オートマトン
がある。
また、ソフトウェアに相当するものとして、以下がある。
テープに読み書きされる有限個の種類の記号
最初から(初期状態において)テープにあらかじめ書かれている記号列
有限オートマトンの状態遷移規則群。詳細は次で述べる
この有限オートマトンの状態遷移規則は、その有限オートマトンの「現在の状態」(内部状態)と、ヘッドがテープの「現在の場所」から読み出した記号の組み合わせに応じて、次のような動作を実行する。
テープの「現在の場所」に新しい記号を書き込む(あるいは、現在の記号をそのままにしてもよい)
ヘッドを右か左に一つシークする(あるいは、移動しなくてもよい)
有限オートマトンを次の状態に状態遷移させる(同じ状態に遷移してもよい)
さらに、この有限オートマトンには(一般的な有限オートマトンの「受理状態」と同様な)「受理状態」がある。計算可能性理論的には、決定問題の2種類の答えに対応する、2種類の受理状態が必要である。