turing-machines - 构造图灵机来确定ww ^ Rw

Question

w ^ R是w的倒数，w是{0，1} *。因此，TM需要先确定一个单词，然后再确定该单词的反义词，再确定该单词。
我不想要答案，我只是想要一个线索开始并走上正确的道路。

Answer 1

由于已经过去了一段时间并且可能不再需要答案了，我想我将提出一种解决方案，以使将来的学生受益，以寻找一个图灵机如何识别一种语言的示例。

这是主意。我们将带字母{0，1，a，b，c，d}作为带字母，并制作一个可识别w w ^ R w的单带单无限带Turing机。机器将分五个阶段工作:

将前缀w w ^ R中的0和1替换为a和b。

查看w w ^ R是否是回文。

将磁带恢复到原始状态。

用c和d替换后缀w ^ R w中的0和1。

查看w ^ R是否是回文。

请注意，这只是一种简单的方式(据我所知)，它表明存在图灵机可以识别这种语言。自然地，证明在任何与Turing等效的计算系统中都存在一种可以解决此问题的算法同样好(证明存在TM)……不过，这概述了这样一个TM的构造。还要注意，可能存在一个更简单，更有效或更直观的TM来解决此问题...同样，这只是一种方法。

步骤1的工作方式如下:

前提:磁带以空白开头，包含(0 + 1)*中的任何字符串，然后是无限的空白正方形字符串。

后置条件:如果磁带为空或长度不是3的倍数，则暂停；否则为0。否则，磁带以空白开头，后跟(a + b)^ 2n(c + d)^ n，然后是无限的空白字符串。

向右移动。

如果为空，则停止接受。否则，向右扫描，直到找到一个空的胶带方块，然后向左移动。

如果0，则将磁带更改为c；如果1，则将磁带更改为d。

向左扫描，直到找到一个空的胶带方块。向右移。

如果磁带为0或1，则更改为a或b，然后向右移动。如果磁带是c或d，则停止剔除。

如果磁带为0或1，则更改为a或b，然后向右移动。如果磁带是c或d，则停止剔除。

如果磁带是c或d，请扫描到磁带的开头并转到步骤2。否则，向右扫描直到c或d，然后向左移动。

如果0，则将磁带更改为c；如果1，则将磁带更改为d。

向左扫描，直到找到a或b。向右移。

从4开始重复。

步骤2的工作方式如下:

前提:磁带以空白开头，后跟(a + b)^ 2n(c + d)^ n，然后是无限的空白字符串。

后置条件:如果前缀(a + b)^ 2n不是回文，则停止；否则，将磁带保持在类似D(c + d)^ 3n D *的状态

向右移动。

如果磁带是a(或b)，请向右移动。如果磁带是c或d，请转到磁带的开头，然后转到步骤3。

如果磁带是c，d或空白，则停止拒绝。否则，请向右扫描，直到找到c，d或空白。向左移动。

如果磁带是b(或a)，则停止拒绝。否则，将其更改为c(或d)并向左扫描，直到看到空白，c或d。向右移。将a(或b)更改为c(或d)。向右移。

从步骤2开始重复。

步骤3的工作方式如下

前提:磁带为D(c + d)^ 3n D *

后置条件:磁带为D(0 + 1)^ 3n D *

向右移动。

如果磁带是c，则写0并向右移动。如果录像带是d，则写1并向右移动。如果磁带为空白，请移至磁带末尾的第一个空白处，然后转到步骤4。

重复步骤2。

第4步和第5步的工作方式与第1步和第2步的工作原理相同，只是您向后工作(磁带现在看起来像D(c + d)^ n(a + b)^ 2n D *，并且您必须检查是否(a + b)^ 2n部分是回文。

通过这两个测试的任何字符串都必须采用w w ^ R w的形式，其中w在(0 + 1)*中。