我的任务是为语言构建一个枚举器（一个图灵机器，它也会打印到输出磁带并通过进入print状态输出），其中：
1）状态数必须不超过10个（包括{0 ^ (3 ^ n) | n >= 0}和print状态，它们是10个状态的一部分）
2）halt，打印机字母表为Gamma，仅此而已。
3）输出磁带字母表为{0, x, space}。
我试过无数次，试图建立它与最多10个州，但设法使用11，而不是10。我的想法是用一个空格擦除每个{0}，然后遍历一个特定的分隔符，比如0，并在分隔符之前为每个删除的X写3个0s。例如0。space|x|space,space,space|x|000000000|x|只是为了强调这个问题的分隔符，空格是前一个被覆盖的-在用"|"覆盖每个0's之后，我将遍历0并在最后附加3space。
每次我失败的时候，我都悲惨地失去了一个国家。我已经没有主意了…帮帮我？
谢谢
最佳答案
有很多机器可以做到这一点。这里有一个例子。它的状态数恰好比要求的要少。
基本思想是：
首先将0^(3^0) = 0^1 = 0打印到磁带上。
执行此操作后，立即输入print，因为0是我们需要枚举的字符串。
打印后，将磁带上的所有0转换为空格，从左到右读取
将所有0转换为空格后，将最右边的空格转换为0，然后在磁带末尾添加两个0。
继续第4步，直到删除所有空格
磁带内容是一个新的要枚举的字符串，因为我们采用了以前的0^(3^n)格式的字符串，并将每次出现的0都增加了三倍，从而得到了字符串0^(3^(n+1))。
美国看起来像这样：
Q T Q' T' Mv
-- -- -- -- --
q0 x pr 0 same
print 0 q1 sp same
q1 0 q1 sp right
q1 x q2 x left
q2 x pr x right
q2 sp q3 0 right
q2 0 q2 0 left
q2 x pr x right
q3 0 q3 0 right
q3 x q4 0 right
q4 x q2 0 left
下面是通过打印得到的结果：
xxxxxxxxxxxxxxxxxxxx
^ q0
x0xxxxxxxxxxxxxxxxxx
^ pr
x xxxxxxxxxxxxxxxxxx
^ q1
x xxxxxxxxxxxxxxxxxx
^ q1
x xxxxxxxxxxxxxxxxxx
^ q2
x0xxxxxxxxxxxxxxxxxx
^ q3
x00xxxxxxxxxxxxxxxxx
^ q4
x000xxxxxxxxxxxxxxxx
^ q2
x000xxxxxxxxxxxxxxxx
^ q2
x000xxxxxxxxxxxxxxxx
^ q2
x000xxxxxxxxxxxxxxxx
^ q2
x000xxxxxxxxxxxxxxxx
^ pr
x 00xxxxxxxxxxxxxxxx
^ q1
x 0xxxxxxxxxxxxxxxx
^ q1
x xxxxxxxxxxxxxxxx
^ q1
x xxxxxxxxxxxxxxxx
^ q2
x 0xxxxxxxxxxxxxxxx
^ q3
x 00xxxxxxxxxxxxxxx
^ q4
x 000xxxxxxxxxxxxxx
^ q2
x 000xxxxxxxxxxxxxx
^ q2
x 000xxxxxxxxxxxxxx
^ q2
x 0000xxxxxxxxxxxxxx
^ q3
x 0000xxxxxxxxxxxxxx
^ q3
x 0000xxxxxxxxxxxxxx
^ q3
x 0000xxxxxxxxxxxxxx
^ q3
x 00000xxxxxxxxxxxxx
^ q4
x 000000xxxxxxxxxxxx
^ q2
...
x 000000xxxxxxxxxxxx
^ q2
x0000000xxxxxxxxxxxx
^ q3
...
x0000000xxxxxxxxxxxx
^ q3
x00000000xxxxxxxxxxx
^ q4
x000000000xxxxxxxxxx
^ q2
...
x000000000xxxxxxxxxx
^
x000000000xxxxxxxxxx
^ pr
...