「状態」ではなく「ステップ」を使用しているため、混乱が生じる可能性があると思います。マシンの状態は、メモリ内にある値と考えることができます (ただし、以前の投稿者が指摘したように、テープの内容を含めるためにマシンの状態を取る人もいますが、その定義は関係ないと思います)。あなたの質問に）。この用語の変更が混乱の中心にある可能性があります。あなたが考えていると思うことを説明させてください。:)
5 つの数字のリストを指定しました。たとえば、(1,0,1,1,2) です。あなたが正しく述べているように、これは（左から右に読んで）「マシンが状態1にあり、現在の正方形に0が含まれている場合、1を出力し、右に移動して状態2に変更する」と解釈する必要があります。ただし、「ステップ」という言葉の使用は、「ステップ 2」の後に「ステップ 3」などが続く必要があることを示唆しているように思われますが、実際には、チューリング マシンは状態間を行き来することができます (もちろん、有限個の可能な状態しかあり得ない)。
だからあなたの質問に答えるために：
- チューリング マシンは、「ステップ」ではなく「状態」を追跡します。
- あなたが説明したのは、正当なチューリング マシンです。
- より単純な (そうでなければ面白くない) チューリング マシンは、HALT 状態で開始するマシンです。
編集: 文法、フォーマット、チューリング マシンの不要な説明を削除。
コメントへの返信: あなたのコメントを誤解している場合は訂正してください。ただし、チューリング マシンが一度に複数の状態になる可能性があることを示唆するつもりはありません。可能な状態の数は任意の有限数である可能性があるだけです。たとえば、3 ステート マシンの場合、可能な状態 A、B、C にラベルを付けることができます (提供した例では、2 つの可能な状態に「1」と「2」のラベルを付けました)。これらの値 (状態) の 1 つだけがマシンのメモリに格納されます。「マシンは状態 A にある」または「マシンは状態 B にある」などと言うでしょう (マシンは状態 '1' で開始し、状態 '2' に入った後に終了します)。
また、「よりシンプル/最も」なマシンが何を意味するのか、私にはもはや明確ではありません。知られている最小のユニバーサル チューリング マシン (つまり、適切なテープがあれば、別のチューリング マシンをシミュレートできるチューリング マシン) には、2 つの状態と 5 つのシンボルが必要です (関連するウィキペディアの記事を参照してください)。
一方、同じ計算能力を備えたチューリング マシンよりも単純なものを探している場合は、ポスト チューリング マシンに興味があるかもしれません。