{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:15Z","timestamp":1781078175344,"version":"3.54.1"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,9,29]],"date-time":"2020-09-29T00:00:00Z","timestamp":1601337600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2020,9,29]]},"abstract":"<jats:p>The Busy Beaver function, with its incomprehensibly rapid growth, has captivated generations of computer scientists, mathematicians, and hobbyists. In this survey, I o er a personal view of the BB function 58 years after its introduction, emphasizing lesser-known insights, recent progress, and especially favorite open problems. Examples of such problems include: when does the BB function rst exceed the Ackermann function? Is the value of BB(20) independent of set theory? Can we prove that BB(n + 1) &gt; 2BB(n) for large enough n? Given BB(n), how many advice bits are needed to compute BB(n + 1)? Do all Busy Beavers halt on all inputs, not just the 0 input? Is it decidable, given n, whether BB(n) is even or odd?<\/jats:p>","DOI":"10.1145\/3427361.3427369","type":"journal-article","created":{"date-parts":[[2020,9,29]],"date-time":"2020-09-29T22:04:58Z","timestamp":1601417098000},"page":"32-54","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["The Busy Beaver Frontier"],"prefix":"10.1145","volume":"51","author":[{"given":"Scott","family":"Aaronson","sequence":"first","affiliation":[{"name":"University of Texas at Austin, Austin, TX, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,9,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-001-1052-0"},{"issue":"162","key":"e_1_2_1_2_1","first-page":"665","article-title":"The determination of the value of Rado's noncomputable function (k) for four-state Turing machines","volume":"40","author":"Brady A. H.","year":"1983","unstructured":"A. H. Brady . The determination of the value of Rado's noncomputable function (k) for four-state Turing machines . Mathematics of Computation , 40 ( 162 ):647{ 665 , 1983 . A. H. Brady. The determination of the value of Rado's noncomputable function (k) for four-state Turing machines. Mathematics of Computation, 40(162):647{665, 1983.","journal-title":"Mathematics of Computation"},{"key":"e_1_2_1_4_1","volume-title":"Proc. 1972 Number Theory Conference","author":"Conway J. H.","year":"1972","unstructured":"J. H. Conway . Unpredictable iterations . In Proc. 1972 Number Theory Conference , University of Colorado, Boulder, pages 49{52 , 1972 . J. H. Conway. Unpredictable iterations. In Proc. 1972 Number Theory Conference, University of Colorado, Boulder, pages 49{52, 1972."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.2307\/2268019"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/SWCT.1964.3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/14.4.285"},{"key":"e_1_2_1_8_1","volume-title":"Busy Beaver Problem. Bachelors thesis","author":"Kropitz P.","year":"2011","unstructured":"P. Kropitz . Busy Beaver Problem. Bachelors thesis , Charles University in Prague, 2011 . In Czech. https:\/\/is.cuni.cz\/webapps\/zzp\/detail\/49210\/. P. Kropitz. Busy Beaver Problem. Bachelors thesis, Charles University in Prague, 2011. In Czech. https:\/\/is.cuni.cz\/webapps\/zzp\/detail\/49210\/."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/321264.321270"},{"key":"e_1_2_1_10_1","first-page":"247","article-title":"Attacking the Busy Beaver 5","volume":"40","author":"Marxen H.","year":"1990","unstructured":"H. Marxen and J. Buntrock . Attacking the Busy Beaver 5 . Bulletin of the EATCS , 40 : 247 {251, 1990 . http:\/\/turbotm.de\/~heiner\/BB\/mabu90.html. H. Marxen and J. Buntrock. Attacking the Busy Beaver 5. Bulletin of the EATCS, 40:247{251, 1990. http:\/\/turbotm.de\/~heiner\/BB\/mabu90.html.","journal-title":"Bulletin of the EATCS"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01409968"},{"key":"e_1_2_1_12_1","volume-title":"The Busy Beaver competition: a historical survey. https:\/\/arxiv.org\/abs\/0906. 3749","author":"Michel P.","year":"2019","unstructured":"P. Michel . The Busy Beaver competition: a historical survey. https:\/\/arxiv.org\/abs\/0906. 3749 , 2019 . P. Michel. The Busy Beaver competition: a historical survey. https:\/\/arxiv.org\/abs\/0906. 3749, 2019."},{"issue":"3","key":"e_1_2_1_13_1","first-page":"884","article-title":"On non-computable functions","volume":"41","author":"T.","year":"1962","unstructured":"T. Rad--o . On non-computable functions . Bell System Technical Journal , 41 ( 3 ):877{ 884 , 1962 . https:\/\/archive.org\/details\/bstj41--3--877\/mode\/2up. T. Rad--o. On non-computable functions. Bell System Technical Journal, 41(3):877{884, 1962. https:\/\/archive.org\/details\/bstj41--3--877\/mode\/2up.","journal-title":"Bell System Technical Journal"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1978-0491103-7"},{"key":"e_1_2_1_15_1","volume-title":"A relatively small Turing machine whose behavior is independent of set theory. Complex Systems, (25):4","author":"Yedidia A.","year":"2016","unstructured":"A. Yedidia and S. Aaronson . A relatively small Turing machine whose behavior is independent of set theory. Complex Systems, (25):4 , 2016 . https:\/\/arxiv.org\/abs\/1605.04343. A. Yedidia and S. Aaronson. A relatively small Turing machine whose behavior is independent of set theory. Complex Systems, (25):4, 2016. https:\/\/arxiv.org\/abs\/1605.04343."}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3427361.3427369","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3427361.3427369","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:26Z","timestamp":1750197746000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3427361.3427369"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,29]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,9,29]]}},"alternative-id":["10.1145\/3427361.3427369"],"URL":"https:\/\/doi.org\/10.1145\/3427361.3427369","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2020,9,29]]},"assertion":[{"value":"2020-09-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}