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

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

2トラックテープです-

  • Upper track −初期の頭の位置の右側にあるセルを表します。

  • Lower track −初期ヘッド位置の左側のセルを逆の順序で表します。

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

機械は初期状態から起動します q0ヘッドは左端マーカー「終了」からスキ​​ャンします。各ステップで、テープの頭の下にある記号を読み取ります。そのテープセルに新しい記号を書き込んでから、ヘッドを1つのテープセルの左または右に移動します。遷移関数は、実行するアクションを決定します。

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

Note −半無限テープを備えたチューリングマシンは、標準のチューリングマシンと同等です。