graph - 在不改变单词的情况下在单带图灵机上找到回文

Question

很容易找到用 (Φ) 代替两端字母的回文。

 ΦabaΦ
 ΦΦbaΦ
 ΦΦbaΦ
 ΦΦbaΦ
 ΦΦbaΦ
 ΦΦbaΦ
 ΦΦbΦΦ
 ΦΦbΦΦ
 ΦΦbΦΦ
 ΦΦΦΦΦ
 ΦΦΦΦΦ
 ΦΦΦΦΦ YES

可以将 a 更改为 A ，并在任务结束时将 A 更改为 a 。但是有人知道如何在不使用其他标志的情况下实现这一目标吗？

Answer 1

移动结束字符可以帮助：

 ΦΦabaΦΦ
 ΦaΦbaΦΦ
 ΦaΦbΦaΦ YES

或者

 ΦΦabbaΦΦ
 ΦaΦbbaΦΦ
 ΦaΦbbΦaΦ
 ΦabΦbΦaΦ
 ΦabΦΦbaΦ YES

Answer 2

您可以将 a 更改为 A，将 b 更改为 B，并且您的结束字符将是大写字母。（取 ascia 值，如果它在大写范围内，你就知道结束了）这假设你的输入完全是小写的。

Answer 3

对于磁带上每个可能的符号（我假设它们是从有限集合中提取的），您需要一个状态，我将其称为“$X_LOOKING”。从左端开始，将您在此处找到的符号 $X 的状态设置为“$X_LOOKING”。向右移动直到到达终点，看看它是否与 $X 匹配。

当您向左移动时，您将不得不停在第二个字母而不是第一个字母处。为此，您可能可以跟踪您在磁带的另一个区域查看了多少个字母。