主题
Search

忙碌的海狸

下载 Mathematica 笔记本下载 Wolfram 笔记本

忙碌的海狸是一种 n-状态、2-颜色 图灵机，它在停止前写入最大数量 Sigma(n) 个 1 (Rado 1962; Lin and Rado 1965; Shallit 1998)。或者，一些作者将忙碌的海狸定义为一种 图灵机，当从初始空白的纸带开始并在停止前，它执行最大步数 S(n) (Wolfram 2002, p. 889)。Lin 和 Rado (1965) 讨论了导致三状态机器解决方案的过程，Brady (1983) 以及 Machlin 和 Stout (1990) 讨论了导致四状态机器解决方案的过程。

BusyBeaverSigma

对于 n=1, 2, ..., Sigma(n)（也称为 Rado 的 sigma 函数）由 1, 4, 6, 13, ... 给出 (OEIS A028444; Rado 1962; Wolfram 2002, p. 889)。接下来的几项未知，但已构建示例，给出了 Sigma(5)>=4098 和 Sigma(6)>=1.29×10^(865) 的下限 (Marxen)。上面的图示展示了一个 3 状态图灵机，其最大 Sigma(3)=6 (Lin 和 Rado 1965, Shallit 1998)。

BusyBeaverS

n 状态 2 色图灵机（不一定是产生最大数量 1 的同一图灵机）在停止前可以执行的最大步数 n S(n) 的前几项为 1, 6, 21, 107, ... (OEIS A060843; Wolfram 2002, p. 889)。上面展示了对于 n=2、3 和 4 给出最大 S(n) 的图灵机。同样，S(n) 的接下来的几项未知，但显式构造给出了下限 S(5)>=47176870。

BusyBeaver5Rules

Marxen 和 Buntrock (1990) 发现的一组 5 状态规则给出了已知的最大值 Sigma(5)=4098 和 S(5)=47176870，如上图所示 (Wolfram 2002, p. 889; Michel)。

2022 年 5 月，Pavel Kropitz 构建了一个 6 状态 2 符号 图灵机，它大约需要

10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 10 ^ 4.023873729

(或在 Knuth 上箭头表示法 中 >10^^15；Ligocki 2022) 个时间步才能停止（其中指数运算是右结合的，因此最右边的指数运算首先应用），并且已经写入了

(3 ^ ((3 ^ ((3 ^ ((3 ^ ((3 ^ ((3 ^ ((3 ^ ((3 ^ ((3 ^ ((3 ^ ((3 ^ ((3 ^ ((3 ^ ((3 ^ ((3 ^ ((3 ^ (4)+7)/8)+21)/8)+7)/8)+23)/8)+7)/8)+21)/8)+7)/8)+23)/8)+7)/8)+23)/8)+7)/8)+21)/8)+7)/8)+23)/8)+13)/8)-11)/2

当机器停止时写入 1 (Goucher 2022, Ligocki 2022)。

2004 年，Brady 探索了 3 状态、3 色 图灵机，并发现 92649163 为 S(3,3) 的下限。

最佳已知结果的表格由 Michel (2008) 维护。

另请参阅

停机问题, 图灵机

使用 Wolfram|Alpha 探索

参考文献

Barwise, J. 和 Etchemendy, J. "图灵机"。 http://www-csli.stanford.edu/hp/Turing1.html。Brady, A. H. "关于 k=4 值时 Rado 的 Sigma(k) 的猜想最高得分机器 k=4。" IEEE Trans. Elec. Comput. EC-15, 802-803, 1966。Brady, A. H. "关于四状态图灵机时 Rado 的不可计算函数 Sigma(k) 的值的确定。" Math. Comput. 40, 647-665, 1983。Brady, A. H. "Tibor Rado 的忙碌的海狸问题（'忙碌的海狸游戏'）。" http://www.cs.unr.edu/~al/BusyBeaver.html。Brady, A. H. "这是 S(3,3) 的新的忙碌的海狸下限吗？ S(3,3)?" http://www.cs.unr.edu/~al/s3x3-new-value.html。Chaitin, G. J. "计算忙碌的海狸函数。" §4.4 in 通信和计算中的开放问题 (Ed. T. M. Cover 和 B. Gopinath)。纽约：Springer-Verlag, pp. 108-112, 1987。Dewdney, A. K. "计算机娱乐：忙碌的海狸的计算机陷阱，最努力工作的图灵机。" Sci. Amer. 251, 19-23, Aug. 1984。Dewdney, A. K. "计算机娱乐。" Sci. Amer. 252, 12-16, Apr. 1985。Goucher, A. "四次迭代机器。" Jun. 23, 2022. https://cp4space.hatsya.com/2022/06/23/tetrational-machines/。Green, M. W. "关于二元图灵机时 Rado 的 Sigma 函数的下限。" Switching Circuit Theory and Logical Design, Proceedings of the Fifth Annual Symposium, Princeton University, Princeton, NJ, November 11-13, 1964. 纽约：IEEE, pp. 91-94, 1964。Herken, R. 通用图灵机：半个世纪的调查。 牛津，英格兰：Oxford University Press, 1988。Kleene, S. C. 元数学导论。 普林斯顿，新泽西州：Van Nostrand, 1964。Ligocki, S. "BB(6,2)>10^^15。" Jun. 21, 2022. https://www.sligocki.com//2022/06/21/bb-6-2-t15.html。Lin, S. 和 Rado, T. "图灵机问题的计算机研究。" J. ACM 12, 196-212, 1965。Machlin, R. 和 Stout, Q. F. "简单机器的复杂行为。" Physica 42D, 85-98, 1990. http://www.eecs.umich.edu/~qstout/abs/busyb.html。Marxen, H. "忙碌的海狸。" http://www.drb.insel.de/~heiner/BB/。Marxen, H. 和 Buntrock, J. "攻击忙碌的海狸 5。" Bull. EATCS 40, 247-251, Feb. 1990。Michel, P. "忙碌的海狸竞赛。" Feb. 2005. http://www.logique.jussieu.fr/~michel/bbc.html。Michel, P. "忙碌的海狸的历史调查。" https://webusers.imj-prg.fr/~pascal.michel/ha.html#tm62。Rado, T. "关于不可计算函数。" Bell System Technical J. 41, 877-884, May 1962。Shallit, J. "忙碌的海狸问题。" Winter 1998. http://grail.cba.csuohio.edu/~somos/beaver.ps。Sloane, N. J. A. "整数序列在线百科全书"中的序列 A028444 和 A060843。Somos, M. "忙碌的海狸图灵机。" http://grail.cba.csuohio.edu/~somos/bb.html。Wolfram, S. 一种新科学。 香槟市，伊利诺伊州：Wolfram Media, pp. 889 和 1144, 2002。

在 Wolfram|Alpha 中被引用

忙碌的海狸

请引用为

Weisstein, Eric W. "忙碌的海狸。" 来自 MathWorld——Wolfram 网络资源。 https://mathworld.net.cn/BusyBeaver.html

学科分类