Automata-theory-semi-infinite-tape-turing-machine

半無限テープチューリングマシン

半無限のテープを使用したチューリングマシンには、左端があり右端はありません。 左端はエンドマーカーで制限されています。

半無限テープ

それは2トラックのテープです-

• 上部トラック-最初の頭の位置の右側のセルを表します。
• 下部トラック-最初のヘッド位置の左側のセルを逆の順序で表します。

無限長の入力文字列は、最初は連続したテープセルでテープに書き込まれます。

マシンは初期状態* q〜0〜*から起動し、ヘッドは左エンドマーカー「End」からスキ​​ャンします。 各ステップで、テープの頭の下のシンボルを読み取ります。 そのテープセルに新しいシンボルを書き込み、ヘッドを左または右の1つのテープセルに移動します。 遷移関数は、実行するアクションを決定します。

*accept state* および *reject state* という2つの特別な状態があります。 任意の時点で受け入れ状態になった場合、入力は受け入れられ、拒否状態になった場合、入力はTMによって拒否されます。 場合によっては、特定の入力シンボルに対して受け入れられたり拒否されたりすることなく、無限に実行し続けます。

注-半無限テープ付きのチューリングマシンは、標準のチューリングマシンと同等です。