1^3^n 对于 n>=1 图灵机
1^3^n for n>=1 turing machine
我想制作一个接受 1 的 3 次幂字符串的图灵机。111、111111111、111111111111111111111111111，等等。但我无法为此制定算法。到目前为止，我能够制造接受长度为 3 的倍数的机器。请帮助我
检查输入的长度 (111, 111111111,...) 说 strLen。
检查以 3 为底的 log(strLen) 的结果是否等于一个整数。
即在代码中：
bool is_integer(float k)
{
return std::floor(k) == k;
}
if(is_integer(log(strLen)/log(3))){
//Then accept the string as it's length is a power of 3.
}
与任何编程任务一样，您的目标是将任务分解为您可以解决的更小的问题，解决这些问题，然后将各个部分组合在一起以解决更难的问题。一般来说，有很多方法可以做到这一点，您只需要找到一种对您有意义的方法即可。然后，也只有到那时，您才应该担心获得 "better"、"faster" 程序。
什么是 3 的幂？
- 一是三的幂(3^0)
- 如果一个数是三的幂，那么这个数的三倍就是三的幂 (x = 3^k => 3x = 3^(k+1))。
我们可以"reverse"上面2的方向给出一个递归的，而不是归纳的定义：一个数是3的幂，如果它能被3整除，并且这个数被3整除是a三的幂：(3 | x && x / 3 = 3^k => x = 3^(k+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
其中可能有一些错误，但我认为这个想法基本上是正确的。
我想制作一个接受 1 的 3 次幂字符串的图灵机。111、111111111、111111111111111111111111111，等等。但我无法为此制定算法。到目前为止，我能够制造接受长度为 3 的倍数的机器。请帮助我
检查输入的长度 (111, 111111111,...) 说 strLen。 检查以 3 为底的 log(strLen) 的结果是否等于一个整数。
即在代码中：
bool is_integer(float k)
{
return std::floor(k) == k;
}
if(is_integer(log(strLen)/log(3))){
//Then accept the string as it's length is a power of 3.
}
与任何编程任务一样，您的目标是将任务分解为您可以解决的更小的问题，解决这些问题，然后将各个部分组合在一起以解决更难的问题。一般来说，有很多方法可以做到这一点，您只需要找到一种对您有意义的方法即可。然后，也只有到那时，您才应该担心获得 "better"、"faster" 程序。
什么是 3 的幂？
- 一是三的幂(3^0)
- 如果一个数是三的幂，那么这个数的三倍就是三的幂 (x = 3^k => 3x = 3^(k+1))。
我们可以"reverse"上面2的方向给出一个递归的，而不是归纳的定义：一个数是3的幂，如果它能被3整除，并且这个数被3整除是a三的幂：(3 | x && x / 3 = 3^k => x = 3^(k+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
其中可能有一些错误，但我认为这个想法基本上是正确的。