computation-theory - 1^3^n 对于 n>=1 图灵机

Question

我想制作一台图灵机，它接受长度为3的1的幂的字符串。111、111111111、111111111111111111111111111等。但我无法为此制定算法。到目前为止，我能够制作接受 3 倍数长度的机器。请帮助我

Answer 1

与任何编程任务一样，您的目标是将任务分解为您可以解决的较小问题，解决这些问题，然后将各个部分组合在一起以解决更难的问题。一般来说，有很多方法可以做到这一点，您只需找到一种对您有意义的方法即可。然后，也只有到那时，您才应该担心获得“更好”、“更快”的程序。

什么使一个数成为三的幂？

1. 数字一是三的幂 (3^0)
2. 如果一个数字是 3 的幂，则该数字的三倍就是 3 的幂 (x = 3^k => 3x = 3^(k+1))。

我们可以“反转”上面 2 的方向，给出一个递归定义，而不是归纳定义:如果一个数能被 3 整除，则该数是 3 的幂，并且除以 3 的数是 3 的幂: (3 | x && x/3 = 3^k => x = 3^(k+1))。

这表明图灵机的工作原理如下:

1. 检查磁带是否只有一个。如果是，则停止接受。
2. 否则，除以三，将磁带头重置到开头，然后重新开始。

如何除以三？好吧，我们可以数一个1，然后删除后面的两个；假设我们最终删除的数量是我们计算的两倍，那么我们的数量将恰好是原始数量的三分之一。然而，如果我们用完了要删除的数字，我们就知道该数字不能被三整除，并且我们可以停止拒绝。

这是我们的设计。现在是实现的时候了。我们将分为两个阶段:第一阶段将检查单个的情况；另一个阶段将除以三并重置磁带头。当我们划分时，我们将通过引入一个新的磁带符号 B 来删除那些，我们可以将其与空白单元格#区分开来。这很重要，这样我们就可以记住输入的开始和结束位置。

Q    T    |    Q'    T'    D
----------+-----------------
// phase one: check for 3^0
----------+-----------------
q0   #    |    h_r   #     S    // empty tape, not a power of three
q0   1    |    q1    1     R    // see the required one
q0   B    |    h_r   B     S    // unreachable configuration; invalid tape
q1   #    |    h_a   #     L    // saw a single one; 1 = 3^0, accept
q1   1    |    q2    1     L    // saw another one; must divide by 3
q1   B    |    q1    B     R    // ignore previously erased ones
----------+-----------------
// prepare for phase two
----------+-----------------
q2   #    |    q3    #     R    // reached beginning of tape
q2   1    |    q2    1     L    // ignore tape and move left
q2   B    |    q2    B     L    // ignore tape and move left
----------------------------
// phase two: divide by 3
----------------------------
q3   #    |    q6    #     L    // dividing completed successfully
q3   1    |    q4    1     R    // see the 1st one
q3   B    |    q3    B     R    // ignore previously erased ones
q4   #    |    h_r   #     S    // dividing fails; missing 2nd one
q4   1    |    q5    B     R    // see the 2nd one
q4   B    |    q4    B     R    // ignore previously erased ones
q5   #    |    h_r   #     S    // dividing fails; missing 3rd one
q5   1    |    q3    B     R    // see the 3rd one
q5   B    |    q5    B     R    // ignore previously erased one
----------+-----------------
// prepare for phase one
----------+-----------------
q6   #    |    q0    #     R    // reached beginning of tape
q6   1    |    q6    1     L    // ignore tape and move left
q6   B    |    q6    B     L    // ignore tape and move left

其中可能存在一些错误，但我认为这个想法基本上应该是合理的。