algorithm - 为什么 N-State 忙碌的海狸不能一直向右走？

Question

我正在阅读有关 Busy Beavers 的文章，但如果他们有无限长的磁带，为什么他们不能一直向右无限打印 1？为什么他们要一直左转右转

Answer 1

由于我的评论可能不足以解决您的问题，因此我会稍微详细说明一下。你 build 了一个只向右移动的忙碌的海狸吗？让我们尝试 N = 2:

• 状态 A，磁带 0 ==> 写 1，向右移动，转到状态 A/B(选择你喜欢的)
• 状态B，磁带0 ==>写1，向右移动，进入状态A/B(选择你喜欢的)
• (磁带 1 的定义无关紧要，仅在向右移动时不会发生)

可以看到这样会写很多的!但它永远不会停止，游戏规则是编写一个停止的图灵机。

所以我们必须修改它来停止:

• 状态A，磁带0 ==>写1，向右移动，进入状态B
• 状态 B，磁带 0 ==> 写入 1，向右移动，进入状态 HALT
• (带 1 的定义无关紧要，不会发生这种情况)

但现在我们可以看到我们是多么低效，完全忽略了很多可用的选项。因此，我们将向左移动添加到我们的武器库中以提高效率。我现在将简写符号，希望它更容易阅读。

• A, 0 => 1, 右, B
• B, 0 => 1, Left, A(我们必须在这里向左走以避免永远停止)
• A, 1 => 1, 左, B
• B, 1 => 1, , HALT(最后一个选项，必须是暂停)

所以我们得到的执行是:

1. ...0 0 0 0 0..., A => 1, 右, B
2. ...0 0 1 0 0..., B => 1, 左, A
3. ...0 0 1 1 0..., A => 1, 左, B
4. ...0 0 1 1 0..., B => 1, 左, A
5. ...0 1 1 1 0..., A => 1, 右, B
6. ...1 1 1 1 0..., B => 1, , 暂停

因此最终磁带在 6 个步骤后有 4 个 1，这比我们只向右移动时获得的结果要好得多。