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

Question

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

如果它采取的第一个动作包括倒带，它会回到起点，还是这是一个特例，它会保持在起点？

Answer 1

图灵机中的磁带在两个方向上都是无限的；通常假设开始之前的所有内容都充满了0。

Answer 2

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