turing-machines - 如何将字符串从一个磁带复制到另一个（两个磁带图灵机）？

Question

我必须使用两带图灵机来决定 w#w。我知道你需要复制最后一部分，即 # 之后的部分到第二个磁带上，然后逐个字符比较，看看这两个部分是否相同。

我的问题是如何将 # 之后的那部分复制到第二个磁带上？

有任何想法吗 ？

w = (a|b)^*

Answer 1

除非我遗漏了什么，否则这似乎很微不足道。

您从第一个磁带开始，使用在#遇到 时更改状态的规则。遇到#时，将磁头向右移动，将状态更改为到达磁带末尾时更改的状态，然后开始在第二个磁带上写入第一个磁带上的任何内容。