从方程设计图灵机
Turing machine designing from equation
如何设计以下图灵机概念？ （有一个 'L' 看起来像 '1'）
我的尝试也给出了，但是不正确....
看来您需要一个 TM 来识别这样的字符串：
- 以 X 的 (L+1) 个实例开始
- 继续 Y 的 (L) 个实例
- 以 Z 的 (L+3) 个实例结束
- 对于 L > 0
我们需要一种策略来确保我们的 TM 可以跟踪每个符号的数量。我们可以想象多磁带解决方案会非常简单：
- 使用三个辅助磁带：一个用于计算 X 的实例，一个用于计算 Y 的实例，一个用于计算 Z 的实例
- 从左到右扫描输入磁带，验证 X 在 Y 之前，Y 在 Z 之前，并将符号复制到辅助磁带
- 重置磁头并从左到右扫描，验证以下内容：
- 至少有一个Y
- X正好比Y多一个；也就是说，X 磁带有一个 X 时
你在 Y 磁带上看到第一个空白，当你在 Y 磁带上看到第二个空白时，X 磁带有一个空白
- Z正好比Y多三个；也就是说，当你看到Y带上的第一、第二和第三个空白时，Z带就有一个Z，当你看到Y带上的第四个空白时，Z带就有一个空白
与其尝试写一个多磁带 TM，不如写一个单磁带 TM：
- 划掉 X 和 Y，直到所有 Y 都被划掉，然后验证是否只剩下一个 X
- 解开 Y
- 把Y和Z划掉，直到把所有的Y都划掉，然后验证剩下三个Z
这是一个过渡 table:
q t q' t' d comment
-- --- -- -- ----- -------
q0 X q0 X right move right to find at least one Y
q0 Y q1 V left then cross it out and start looking for an X
q1 U,V q1 U,V left keep looking for an X to cross off
q1 X q2 U right cross off the X and start looking for more Y
q2 U,V q2 U,V right keep looking for more Y to cross off
q2 Y q1 V left we found another Y, cross off and keep going
q2 Z q3 Z left no more Y, start looking for last X
q3 U,V q3 U,V left keep looking for last X
q3 X q4 U left need to make sure this was the last one
q4 # q5 # right it was the last X, go check V & Z now
q5 U q5 U right skip the crossed off X (now U)
q5 V q5 Y right skip crossed off Y, and uncross back to Y
q5 Z q6 W left cross off a Z and start looking for V
q6 V,W q6 V,W left skip any crossed off Y/Z and look for Y
q6 Y q7 V right cross off Y, go look for more Z
q6 U q8 U right no more Y, ensure three uncrossed Z
q7 V,W q7 V,W right skip any crossed off Y/Z and look for Z
q7 Z q6 W left cross off another Z and start looking for Y
q8 V,W q8 V,W right skip any crossed off Y/Z and look for Z
q8 Z q9 W right found one Z, need two more
q9 Z qA W right found a second Z, need one more
qA Z qB W right found a third Z, need zero more
qB # hA # left no more Z, halt-accept
如何设计以下图灵机概念？ （有一个 'L' 看起来像 '1'）
我的尝试也给出了，但是不正确....
看来您需要一个 TM 来识别这样的字符串：
- 以 X 的 (L+1) 个实例开始
- 继续 Y 的 (L) 个实例
- 以 Z 的 (L+3) 个实例结束
- 对于 L > 0
我们需要一种策略来确保我们的 TM 可以跟踪每个符号的数量。我们可以想象多磁带解决方案会非常简单：
- 使用三个辅助磁带：一个用于计算 X 的实例，一个用于计算 Y 的实例，一个用于计算 Z 的实例
- 从左到右扫描输入磁带，验证 X 在 Y 之前，Y 在 Z 之前，并将符号复制到辅助磁带
- 重置磁头并从左到右扫描，验证以下内容：
- 至少有一个Y
- X正好比Y多一个；也就是说，X 磁带有一个 X 时 你在 Y 磁带上看到第一个空白，当你在 Y 磁带上看到第二个空白时，X 磁带有一个空白
- Z正好比Y多三个；也就是说，当你看到Y带上的第一、第二和第三个空白时，Z带就有一个Z，当你看到Y带上的第四个空白时，Z带就有一个空白
与其尝试写一个多磁带 TM，不如写一个单磁带 TM：
- 划掉 X 和 Y，直到所有 Y 都被划掉，然后验证是否只剩下一个 X
- 解开 Y
- 把Y和Z划掉，直到把所有的Y都划掉，然后验证剩下三个Z
这是一个过渡 table:
q t q' t' d comment
-- --- -- -- ----- -------
q0 X q0 X right move right to find at least one Y
q0 Y q1 V left then cross it out and start looking for an X
q1 U,V q1 U,V left keep looking for an X to cross off
q1 X q2 U right cross off the X and start looking for more Y
q2 U,V q2 U,V right keep looking for more Y to cross off
q2 Y q1 V left we found another Y, cross off and keep going
q2 Z q3 Z left no more Y, start looking for last X
q3 U,V q3 U,V left keep looking for last X
q3 X q4 U left need to make sure this was the last one
q4 # q5 # right it was the last X, go check V & Z now
q5 U q5 U right skip the crossed off X (now U)
q5 V q5 Y right skip crossed off Y, and uncross back to Y
q5 Z q6 W left cross off a Z and start looking for V
q6 V,W q6 V,W left skip any crossed off Y/Z and look for Y
q6 Y q7 V right cross off Y, go look for more Z
q6 U q8 U right no more Y, ensure three uncrossed Z
q7 V,W q7 V,W right skip any crossed off Y/Z and look for Z
q7 Z q6 W left cross off another Z and start looking for Y
q8 V,W q8 V,W right skip any crossed off Y/Z and look for Z
q8 Z q9 W right found one Z, need two more
q9 Z qA W right found a second Z, need one more
qA Z qB W right found a third Z, need zero more
qB # hA # left no more Z, halt-accept