圖靈機可以通過磁帶的開頭嗎？

Question

我有一個關於車削機牀的非常簡單的問題。

如果要採取的第一個動作包括倒帶，它是否會移回起始點或者這是一個特殊情況，它會保持在起始點？

Answer 1

圖靈機中的磁帶在兩個方向都是無限的;通常假設在開始之前的所有內容都填入0。

Answer 2

該磁帶無限擴展兩個方向。 Wikipedia有這麼一段話：

一個磁帶被分成一個單元，一個接一個。每個單元格都包含一些有限字母表中的符號。字母表包含一個特殊的空白符號（這裏寫爲'B'）和一個或多個其他符號。假定磁帶可以任意地向左和向右延伸，即，圖靈機總是提供儘可能多的磁帶以滿足其計算。

Answer 3

這真的取決於你使用的是哪種形式。一些形式化的磁帶可以在兩個方向上無限擴展，而另一些則有左端。在左端陣營內，還有更多的細分。有些人說，當機器離開磁帶的左端時，機器發生故障或沒有輸出（我正在考慮哈姆金斯和米亞斯尼科夫停止工作的可能性），而另一些人則在最左邊的磁帶盒中強制一個特殊的，不可修改的標記（Kozen在他的自動機和可計算性教科書中做了這個）。這些形式主義基本上都是相同的，所以大多數人不會對此做出重大處理，只需使用最方便的手頭應用即可。