主題
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) 維護。

另請參閱

停機問題, 圖靈機

使用 探索

參考文獻

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。

在 中被引用

忙碌的海狸

請引用為

Weisstein, Eric W. "忙碌的海狸。" 來自 ——Wolfram 網路資源。 https://mathworld.tw/BusyBeaver.html

學科分類