algorithm - busy beaver 函数是否是 n 状态 busy beaver 游戏所独有的？

Question

对于给定的 n 态 busy beaver game , 是 busy beaver function是唯一的，还是可能有多个功能具有相同的最高分？也许这两种方式都没有得到证明？

Answer 1

是的，是的。

busy beaver 函数定义为

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

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

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

可以计算较小的\Sigma 值；查看 OEIS entry对于最大的已知值。