computer-science - チューリング マシンはテープの先頭を超えることができますか?

Question

ターニング マシンについて非常に簡単な質問があります。

実行する最初のアクションにテープの巻き戻しが含まれる場合、開始点を過ぎて戻るのでしょうか、それともこれは特殊なケースであり、開始点にとどまりますか?

Answer 1

それは、使用している形式に大きく依存します。形式主義の中には、両方向に無限に拡張可能なテープを持つものもあれば、左端を持つものもあります。左端のキャンプ内には、さらに細分化された部分があります。マシンがテープの左端から外れると、マシンが故障したり出力を生成しないと言う人もいます (停止確率に関する Hamkins と Miasnikov の研究について考えています)。 (Kozen は Automata and Computability の教科書でこれを行っています)。これらの形式はすべて本質的に同等であるため、ほとんどの人はそれについて大したことはせず、目前のアプリケーションに最も便利なものを使用します。

Answer 2

チューリング マシンのテープは両方向に無限です。通常、先頭より前のすべてが で満たされていると想定されます0。

Answer 3

テープは両方向に無限に伸ばすことができます。ウィキペディアには次のように書かれています。

セルに分割されたテープ。各セルには、有限のアルファベットの記号が含まれています。アルファベットには、特別な空白の記号（ここでは「B」と表記）と1つ以上の他の記号が含まれています。テープは、左右に任意に拡張可能であると想定されています。つまり、チューリングマシンには、計算に必要なだけのテープが常に供給されます。