チューリング機械 状態の有限集合 ヘッドの方向を表す。 L:1コマ左へ R:1コマ右へ テープ記号の有限集合 入力記号の有限集合 動作関数 初期状態 空白記号 受理状態の有限集合
チューリング機械の1ステップの動作(1) 有限制御部 のとき 状態 … …
有限制御部 に遷移する。 状態 … …
チューリング機械の1ステップの動作(2) 有限制御部 のとき 状態 … …
有限制御部 に遷移する。 状態 … …
初期様相 で定義されているステップから動作を開始して, 有限制御部 状態 … … …
以下,ステップを繰り返し,
動作停止時の様相 のとき, 入力語を受理する。 停止して, 有限制御部 状態 … …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
… …
受理状態で停止したので,M41は入力語aaaabbbbを受理する。 … …
なお, である。
受理状態に遷移したので, M42 は入力語 aaaabbbbaaaa を受理する。
である。