构造一个图灵机来决定 ww^Rw
w^R 是 w 的逆，w 是 {0, 1}* 。因此，TM 需要决定一个单词，然后是该单词的反义词，然后是该单词。 我不想要答案，我只想要一个开始并走上正确轨道的线索。
w^R is the reverse of w and w is {0, 1}* . So the TM needs to decide a word followed by the reverse of this word followed by the word.
I don't want the answer, I just want a lead to start and to get on the right track.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
由于一段时间过去了，可能不再需要答案，我想我会提出一个解决方案，以方便未来寻找图灵机如何识别一种语言的示例的学生。
这是我的想法。我们将采用磁带字母表 {0, 1, a, b, c, d} 并制作一个识别 ww^R w 的单磁带单无限磁带图灵机。该机器将分五个阶段工作：
请注意，这只是一种简单的（对我来说是可以理解的）方法来表明存在图灵机来识别这种语言。当然，证明在任何图灵等效计算系统中存在一种算法来解决这个问题也同样好（它证明了存在一个TM）......不过，这概述了一个这样的TM的构造。另请注意，可能有一个更简单、更高效或更直观的 TM 来解决这个问题……再次强调，这只是一种方法。
第 1 步的工作原理如下：
后置条件：如果磁带为空或长度不是 3 的倍数，则停止；否则，磁带以空白开始，后面是 (a+b)^2n (c+d)^n，最后是无限的空白字符串。
。步骤 2 的工作原理如下：
后置条件：如果前缀 (a+b)^2n 不是回文，则停止；否则，使磁带处于类似 D (c+d)^3n D*
的状态
步骤 3 的工作方式如下
后置条件：磁带为 D (0+1)^3n D*
步骤 4 和 5 的工作方式与步骤 1 和 2 类似，只是向后操作（磁带现在看起来像 D (c +d)^n (a+b)^2n D*，并且您必须检查 (a+b)^2n 部分是否是回文。
通过这两项测试的任何字符串都必须采用 ww^R w 的形式。其中 w位于 (0+1)* 中。
Since some time has passed and the answer probably isn't needed anymore, I guess I'll propose a solution for the benefit of future students looking for an example of how one language can be recognized by a Turing machine.
Here's the idea. We'll take as the tape alphabet {0, 1, a, b, c, d} and make a single-tape singly-infinite tape Turing machine that recognizes w w^R w. The machine will work in five phases:
Note that this is simply one easy (for me to understand, that is) way to show that there exists a Turing machine to recognize this language. Naturally, showing that there exists an algorithm to solve this in any Turing-equivalent system of computation is just as good (it proves there exists a TM)... still, this outlines the construction of one such TM. Also note that there may be a simpler, more efficient or more intuitive TM to solve this problem... again, this is only one approach.
Step 1 will work as follows:
Postcondition: Halts if tape is empty or if length is not a multiple of 3; else, the tape begins with a blank, is followed by (a+b)^2n (c+d)^n, followed by an infinite string of blanks.
Step 2 will work as follows:
Postcondition: Halts if the prefix (a+b)^2n isn't a palindrome; otherwise, leaves the tape in a state like D (c+d)^3n D*
Step 3 will work as follows
Postcondition: Tape is D (0+1)^3n D*
Step 4 and 5 work just like steps 1 and 2, except you work backwards (the tape now looks like D (c+d)^n (a+b)^2n D*, and you must check to see whether the (a+b)^2n part is a palindrome.
Any string passing both these tests must be of the form w w^R w where w is in (0+1)*.
作为提示，请注意对于某些 n，wwRw 的长度必须为 3n（因为每个字符恰好出现 3 次）。因此，您可以构建一台图灵机，它通过某种方式计算字符串的长度，使用它来确定三个字符串的边界在哪里，然后检查这三个部分是否都具有适当的组成。如果您无法算出 3 个字符的倍数，您可以立即拒绝。
根据允许的 TM 类型，使用多轨或多磁带图灵机可能是最简单的，这样您就可以用一些额外的信息来标记字母。
希望这有帮助！
As a hint, note that wwRw must have length 3n for some n (since each character appears exactly three times). You might therefore build a Turing machine that works by somehow counting the length of the string, using this to determine where the boundaries of the three strings are, and then checking that the three pieces all have the appropriate composition. If you can't count up a multiple of 3 characters, you could immediately reject.
Depending on what sort of TM is allowed, this might be easiest with a multitrack or multitape Turing machine so that you can mark up the letters with some extra information.
Hope this helps!
以下是我使用 2 个磁带和 O(n) 复杂度的方法：
Here's how I did it with 2 tapes and O(n) complexity: