右图灵机
我要求检查只能向右移动（或停留）的图灵机是否等于标准图灵机。
我想将输入复制到另一盘磁带上，不受限制。但这可能吗？
感谢你。
I asked to check if Turing machine that can move only right (or stay) is equal to a standard Turing machine .
I thought to copy the input to another tape, which unrestricted. but is it possible?
thank u.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
考虑这样一个总是终止的 TM，具有 n 个状态和磁带/输入字母表 {0,1}。对于大小为 m 的输入，它必须在最多 2*m*n 步后停止。这是因为它不能在不前进的情况下经历两次读取相同符号的相同状态；如果这样做，它就不会停止。
这意味着此类 TM 可解决的所有问题都在 P 中。另一方面，存在用于解决 EXPTIME 中问题的常规 TM。由于 P 是 EXPTIME 的真子集，因此这两个模型并不等价。
顺便说一句：图灵机通常只有一个磁带，因此复制到不同的磁带不是一种选择。
Consider such a TM that always terminates, has n states and tape/input alphabet of {0,1}. On an input of size m, it must halt after at most 2*m*n steps. That's because it cannot go through the same state reading the same symbol twice without advancing; if it did, it would not halt.
This means all problems solvable by such TM are in P. On the other hand, regular TMs exists for solving problems in EXPTIME. Since P is a proper subset of EXPTIME, the two models are not equivalent.
BTW: A Turing machine usually only has one tape, so copying to a different tape is not an opion.
只能向右移动并保持不动的图灵机是图灵机的变体，并且是标准图灵机的子集。因此本质上它并不像标准图灵机那么强大，但仍然是一个 TM。
此外，组合多个图灵机磁带并不会给您带来更多的计算能力，并且也完全等同于单个标准 TM。
（多个磁带仅在效率方面有优势，而在计算方面没有优势。但由于 TM 不关心效率而只关心可计算性，因此这是无关紧要的）。
A turing machine that could move only right and stay is a variation of the Turing machine and is a subset of the standard turing machine. So essentially it is not as powerful as the standard turing machine but is a TM nonetheless.
Furthermore, combining multiple turing machine tapes does NOT give you more computing power and is also completely equivalent to a single standard TM.
(Multiple tapes are only advantageous in terms of efficiency, not computation. But since TMs not concerned about efficiency but only computability, this is irrelevant).