computer-science - 图灵机可以越过磁带的开头吗？

Question

我有一个关于车床的非常简单的问题。

如果它采取的第一个 Action 包括倒带，它会向后移动超过起点，还是这是一种特殊情况，它会留在起点吗？

Answer 1

这实际上取决于您使用的是哪种形式主义。一些形式主义有一条在两个方向上都可以无限延伸的带子，而另一些则有一个左端。在左端营地内，还有更多的分割。有人说当机器离开磁带的左端时机器发生故障或不产生输出(我想到了 Hamkins 和 Miasnikov 关于停止概率的工作)，而其他人则在最左边的磁带单元中强制使用一个特殊的、不可重写的标记(Kozen 在他的自动机和可计算性教科书中这样做)。这些形式主义在本质上都是等价的，因此大多数人不会在意它，只是使用对手头的应用程序最方便的任何东西。