「チューリングマシン」の版間の差分

*ヘッドを右か左に一つシークする(あるいは、移動しなくてもよい)
*有限オートマトンを次の状態に状態遷移させる(同じ状態に遷移してもよい)
さらに、この有限オートマトンには(一般的な有限オートマトンの「受理状態」と同様な)「受理状態」がある。[[計算可能性理論]]的には、[[決定問題]]の2種類の答えに対応する、2種類の受理状態が必要である<ref group="注釈">あるいは単に停止する場合は、停止する前に、答えがどちらであるかを、テープ上の記号列として書き残してから停止する。</ref>。
 
== 現実の計算との関係 ==