在单带图灵机上查找回文而不改变单词
很容易找到用（Φ）替换两端字母的回文。
ΦabaΦ
ΦΦbaΦ
ΦΦbaΦ
ΦΦbaΦ
ΦΦbaΦ
ΦΦbaΦ
ΦΦbΦΦ
ΦΦbΦΦ
ΦΦbΦΦ
ΦΦΦΦΦ
ΦΦΦΦΦ
ΦΦΦΦΦ YES
可以将 a 更改为 A ，并在任务结束时将 A 更改为 a 。但是有人知道如何在不使用额外标志的情况下实现这一目标吗？
It is quite easy to find palindrome replacing letters on both ends with (Φ).
ΦabaΦ
ΦΦbaΦ
ΦΦbaΦ
ΦΦbaΦ
ΦΦbaΦ
ΦΦbaΦ
ΦΦbΦΦ
ΦΦbΦΦ
ΦΦbΦΦ
ΦΦΦΦΦ
ΦΦΦΦΦ
ΦΦΦΦΦ YES
It is possible with changing a to A , and changing A to a at the end of task. But does anybody have an idea ,how to achieve this without using additional signs?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
移动结束字符可以帮助：
或
Moving of end characters can help:
or
您可以将a更改为A，将b更改为B，并且您的结束字符将是大写字母。 （取ascia值，如果落在大写范围内就知道结束了）
这假设您的输入完全是小写。
You can change a to A, and b to B, and ur end character would be a capital letter. (take the ascia value, and if it falls in the uppercase range, you know the end)
This assume your input is entirely lower case.
对于磁带上的每个可能的符号（我假设是从有限集中提取的），您需要一个状态，我将其称为“$X_LOOKING”。从左端开始，将您在此处找到的符号 $X 的状态设置为“$X_LOOKING”。向右移动直到到达末尾并查看它是否与 $X 匹配。
当您向左移动时，您必须停在第二个字母处，而不是第一个字母处。为此，也许您可以跟踪您在磁带的另一个区域上查看过的字母数量。
For each possible symbol on the tape (which I assume are drawn from a finite set), you need a state, which I'll call "$X_LOOKING". Start at the left end and set the state to "$X_LOOKING" for the symbol $X that you find there. Move right until you hit the end and see if it matches $X.
When you move back left, you'll have to stop at the 2nd letter instead of the first. For this maybe you can keep track of how many letters you've looked at on another area of the tape.