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

Question

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

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

Answer 1

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

Answer 2

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

Answer 3

磁带在两个方向上都可以无限延伸。维基百科有这样的说法：

一种磁带，它被分成多个单元，一个接一个。每个单元格都包含来自某个有限字母表的符号。字母表包含一个特殊的空白符号（这里写为“B”）和一个或多个其他符号。假定磁带可任意向左和向右扩展，即，图灵机总是提供其计算所需的尽可能多的磁带。