图灵机 - 学习技巧

Question

我花了整整一个月的时间来解决这个问题，因为我是从练习一书中得到的，我很想知道如何在图灵机中编写这个问题；我真的很想学这个。请问有人可以提供帮助吗？

考虑您登录名的最后两个字母（如果两个字母相同，请选择 拉丁字母表中的下一个字母作为第二个符号）。编写一个图灵机 它将识别语言 Stretch(x+1)。这是所有字符串的语言 包含连续出现的两个字母的字符串，后跟“*”， 后跟另一串字母，每个字母出现 x+1 次，其中 第一个字母串中只出现了一个。这里，x = 1。机器的输入是a、b、*的非空字符串。作为一个 例如，其中字母为“a”和“b”（且 x=1）aba*aabbaa、bb*bbbb 和 baab*bbaaaabb 在该语言中，但 abb*abbb 不在该语言中。你可能会认为你 有在第一个单元格中写入 0 并删除磁带其余部分的子例程 在第一个单元格中写入 1 并删除磁带的其余部分。

如果您能帮助我，我将非常感激。

Answer 1

对每个唯一的字母使用一个堆栈（在您的示例中是两个堆栈）。这没有正式编写或任何内容，但您所要做的就是提供一个算法来证明 TM 可以解决问题。

F1:
FOREACH letter DO
  IF letter = '*' THEN F2
  ELSE push letter twice onto its respective stack

F2:
FOREACH letter DO
  IF tape is empty THEN F3
  IF respective stack is empty THEN *fail state*
  ELSE pop respective stack

F3:
IF both stacks are empty THEN *accept state*
ELSE *fail state*

明白了吗？ TM 证明很有趣。

编辑：作为对您其他帖子的回应，如果您不了解如何构建 TM 证明，您需要阅读一些有关一般证明的内容。我建议迈克尔·西普瑟的简介到计算理论。当你为该文本付出了巨大的努力后，你可以翻到第 137 页来了解有关 TM 的所有内容。