右图灵机

Question

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

我想将输入内容复制到另一个磁带上，不受限制。但是有可能吗？

谢谢你

Answer 1

考虑这样的TM，它总是终止，具有n个状态，并且磁带/输入字母为{0,1}。在大小为m的输入上，它必须在最多2 * m * n个步后停止。这是因为它不能在不前进的情况下经历两次读取相同符号的相同状态。如果这样做，它将不会停止。

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

BTW：图灵机通常只有一盘磁带，因此复制到另一盘磁带上不是选择。

Answer 2

只能向右移动和停留的图灵机是图灵机的一种变体，是标准图灵机的子集。因此，从本质上讲，它不如标准的图腾机强大，但它是TM。

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