algorithm - 忙碌的海狸功能对于 n 状态忙碌的海狸游戏是唯一的吗？

Question

对于给定的 n 状态忙碌海狸游戏，忙碌海狸功能是唯一的，还是可能有多个功能具有相同的最高分数？也许这两种方法都没有被证明？

Answer 1

是的。

繁忙的海狸函数被定义为

\Sigma(n) = max { \sigma(M) | M is a halting n-state 2-symbol Turing machine} 

如果存在，最大值是唯一的，它确实存在（Rado 证明了这一点）。这只是一个数字。

因此 \Sigma(n) 也是唯一的，因此离散函数 \Sigma: N --> N 也是唯一的。可能有多种方法可以将 \Sigma 扩展到连续函数，但为什么有人想要这样做却超出了我的范围。

计算 \Sigma 的小值是可能的；查看OEIS 条目以获取最大的已知值。

Answer 2

正如@PengOne 指出的那样，该功能确实是独一无二的。它是一个完全定义的 N -> N 离散函数。

但是，从您的公式（“或者可能有多个函数具有相同的最高分数”）也可以理解为您想知道是否有多个繁忙的海狸给出相同的最大值。如果是这种情况，那么是的，至少有 2 个忙碌的海狸给定一个 N，一个是通过简单地反转班次从另一个构建而成的。

Answer 3

很久以前就有人问过这个问题，但我发现这很有趣： http: //www.win.tue.nl/~wijers/shallit.pdf

此外，我编写了一个算法来强力解决 3 态忙海狸问题，它给了我大约 22 个非对称配置，产生 6 个符号（连续或不连续）。这意味着如果您考虑可以交换状态 1 和状态 2 以及反转第一个转换，则可能有 60 多种配置。

但这仅适用于产生的符号数量，而不是“最长执行”的符号。