我正在阅读有关 Busy Beavers 的文章，但如果他们有无限长的磁带，为什么他们不能一直向右无限打印 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(最后一个选项，必须是暂停)
所以我们得到的执行是:
- ...0 0 0 0 0..., A => 1, 右, B
- ...0 0 1 0 0..., B => 1, 左, A
- ...0 0 1 1 0..., A => 1, 左, B
- ...0 0 1 1 0..., B => 1, 左, A
- ...0 1 1 1 0..., A => 1, 右, B
- ...1 1 1 1 0..., B => 1,
, 暂停
因此最终磁带在 6 个步骤后有 4 个 1，这比我们只向右移动时获得的结果要好得多。
关于algorithm - 为什么 N-State 忙碌的海狸不能一直向右走？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43599949/