computer-science - 右图灵机

Question

我要求检查只能向右（或停留）移动的图灵机是否等于标准图灵机。

我想将输入复制到另一个不受限制的磁带。但有可能吗？

感谢你。

Answer 1

考虑这样一个 TM 总是终止，有 n 个状态和 {0,1} 的磁带/输入字母表。在大小为 m 的输入上，它必须在最多 2*m*n 步后停止。那是因为它不能通过相同的状态两次读取相同的符号而不前进；如果是这样，它就不会停止。

这意味着此类 TM 可解决的所有问题都在 P 中。另一方面，存在用于解决 EXPTIME 中的问题的常规 TM。由于 P 是 EXPTIME 的真子集，因此这两个模型不等价。

顺便说一句：图灵机通常只有一个磁带，因此复制到不同的磁带不是一种选择。

Answer 2

只能向右移动并保持不动的图灵机是图灵机的一种变体，是标准图灵机的一个子集。所以本质上它没有标准图灵机那么强大，但它仍然是一个 TM。

此外，组合多个图灵机磁带并不会给您更多的计算能力，并且也完全等同于单个标准 TM。

（多磁带仅在效率方面有利，而不是在计算方面。但由于 TM 不关心效率而只关心可计算性，所以这无关紧要）。