{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,12]],"date-time":"2026-07-12T00:12:06Z","timestamp":1783815126137,"version":"3.55.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,8,4]],"date-time":"2025-08-04T00:00:00Z","timestamp":1754265600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,8,4]],"date-time":"2025-08-04T00:00:00Z","timestamp":1754265600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Moldova State University","award":["011301"],"award-info":[{"award-number":["011301"]}]},{"DOI":"10.13039\/100020987","name":"Universit\u00e9 d'\u00c9vry Val-d'Essonne","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100020987","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    The busy beaver game was introduced by Tibor Rad\u00f3 in 1962 and consists in finding the longest halting run that can be achieved by a Turing machine with a given number of states\n                    <jats:italic>n<\/jats:italic>\n                    . The function\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\text {BB}(n)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mtext>BB<\/mml:mtext>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    measuring this length is a well-studied example of an uncomputable function. In this work, we transpose the concept of the busy beaver game to reaction systems\u2014a set rewriting-based model of computing inspired by biochemical reactions. We give a generalized framework for defining various busy beaver challenges and give concrete instantiations for longest runs, periods, preperiods, etc. We further list several busy beaver champions and bounds, depending on what is optimized and what is measured as the size of a reaction system. Finally, we discuss possible implications of our work to thinking about theoretical biology.\n                  <\/jats:p>","DOI":"10.1007\/s11047-025-10037-6","type":"journal-article","created":{"date-parts":[[2025,8,4]],"date-time":"2025-08-04T00:58:47Z","timestamp":1754269127000},"page":"1013-1027","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The busy beaver game for reaction systems"],"prefix":"10.1007","volume":"24","author":[{"given":"Artiom","family":"Alhazov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rudolf","family":"Freund","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sergiu","family":"Ivanov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sergey","family":"Verlan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,8,4]]},"reference":[{"issue":"2","key":"10037_CR1","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/S11047-024-09986-1","volume":"23","author":"A Alhazov","year":"2024","unstructured":"Alhazov A, Freund R, Ivanov S (2024) On the spectrum between reaction systems and string rewriting. Nat Comput 23(2):159\u2013175. https:\/\/doi.org\/10.1007\/S11047-024-09986-1","journal-title":"Nat Comput"},{"issue":"2","key":"10037_CR2","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/S41965-024-00144-1","volume":"6","author":"A Alhazov","year":"2024","unstructured":"Alhazov A, Freund R, Ivanov S, Orellana-Mart\u00edn D, Ram\u00edrez-de-Arellano A, Rodr\u00edguez-Gallego J (2024) P systems with reactive membranes. J Membr Comput 6(2):82\u201393. https:\/\/doi.org\/10.1007\/S41965-024-00144-1","journal-title":"J Membr Comput"},{"issue":"3","key":"10037_CR3","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/S41965-024-00152-1","volume":"6","author":"A Alhazov","year":"2024","unstructured":"Alhazov A, Ivanov S, Orellana-Mart\u00edn D (2024) Queens of the hill. J Membr Comput 6(3):193\u2013201. https:\/\/doi.org\/10.1007\/S41965-024-00152-1","journal-title":"J Membr Comput"},{"issue":"3","key":"10037_CR4","doi-asserted-by":"publisher","first-page":"332","DOI":"10.56415\/csjm.v32.18","volume":"32","author":"A Alhazov","year":"2024","unstructured":"Alhazov A, Ivanov S, Verlan S (2024) A 15-year retrospective on insertion-deletion systems: progress, evolution, and future directions. Comput Sci J Moldova 32(3):332\u2013371","journal-title":"Comput Sci J Moldova"},{"key":"10037_CR5","doi-asserted-by":"publisher","unstructured":"Alhazov A, Aman B, Freund R, Ivanov S (2016) Simulating R systems by P\u00a0systems. In: Leporati, A., Rozenberg, G., Salomaa, A., Zandron, C. (eds.) Membrane Computing - 17th International Conference, CMC 2016, Milan, Italy, July 25-29, 2016, Revised Selected Papers. Lecture Notes in Computer Science, vol 10105, pp 51\u201366. Springer, Berlin, Heidelberg. https:\/\/doi.org\/10.1007\/978-3-319-54072-6_4","DOI":"10.1007\/978-3-319-54072-6_4"},{"key":"10037_CR6","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/J.TCS.2015.11.040","volume":"623","author":"S Azimi","year":"2016","unstructured":"Azimi S, Gratie C, Ivanov S, Manzoni L, Petre I, Porreca AE (2016) Complexity of model checking for reaction systems. Theor Comput Sci 623:103\u2013113. https:\/\/doi.org\/10.1016\/J.TCS.2015.11.040","journal-title":"Theor Comput Sci"},{"key":"10037_CR7","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/J.TCS.2015.02.014","volume":"598","author":"S Azimi","year":"2015","unstructured":"Azimi S, Gratie C, Ivanov S, Petre I (2015) Dependency graphs and mass conservation in reaction systems. Theor Comput Sci 598:23\u201339. https:\/\/doi.org\/10.1016\/J.TCS.2015.02.014","journal-title":"Theor Comput Sci"},{"issue":"3\u20134","key":"10037_CR8","doi-asserted-by":"publisher","first-page":"299","DOI":"10.3233\/FI-2014-1016","volume":"131","author":"S Azimi","year":"2014","unstructured":"Azimi S, Iancu B, Petre I (2014) Reaction system models for the heat shock response. Fundam Informaticae 131(3\u20134):299\u2013312. https:\/\/doi.org\/10.3233\/FI-2014-1016","journal-title":"Fundam Informaticae"},{"key":"10037_CR9","first-page":"259","volume-title":"A half-century survey on the universal turing machine","author":"AH Brady","year":"1988","unstructured":"Brady AH (1988) The busy beaver game and the meaning of life. A half-century survey on the universal turing machine. Oxford University Press, Oxford, pp 259\u2013277"},{"issue":"7","key":"10037_CR10","doi-asserted-by":"publisher","first-page":"1499","DOI":"10.1142\/S0129054111008842","volume":"22","author":"R Brijder","year":"2011","unstructured":"Brijder R, Ehrenfeucht A, Main MG, Rozenberg G (2011) A tour of reaction systems. Int J Found Comput Sci 22(7):1499\u20131517. https:\/\/doi.org\/10.1142\/S0129054111008842","journal-title":"Int J Found Comput Sci"},{"issue":"2\u20133","key":"10037_CR11","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/J.TCS.2006.11.022","volume":"372","author":"M Cavaliere","year":"2007","unstructured":"Cavaliere M, Freund R, Oswald M, Sburlan D (2007) Multiset random context grammars, checkers, and transducers. Theor Comput Sci 372(2\u20133):136\u2013151. https:\/\/doi.org\/10.1016\/J.TCS.2006.11.022","journal-title":"Theor Comput Sci"},{"key":"10037_CR12","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/J.TCS.2015.06.001","volume":"598","author":"A Dennunzio","year":"2015","unstructured":"Dennunzio A, Formenti E, Manzoni L (2015) Reaction systems and extremal combinatorics properties. Theor Comput Sci 598:138\u2013149. https:\/\/doi.org\/10.1016\/J.TCS.2015.06.001","journal-title":"Theor Comput Sci"},{"key":"10037_CR13","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.ic.2019.03.006","volume":"267","author":"A Dennunzio","year":"2019","unstructured":"Dennunzio A, Formenti E, Manzoni L, Porreca AE (2019) Complexity of the dynamics of reaction systems. Inf Comput 267:96\u2013109. https:\/\/doi.org\/10.1016\/j.ic.2019.03.006","journal-title":"Inf Comput"},{"key":"10037_CR14","doi-asserted-by":"publisher","unstructured":"Dennunzio A, Formenti E, Manzoni L, Porreca AE (2015) Ancestors, descendants, and gardens of Eden in reaction systems. Theor Comput Sci 608:16\u201326 https:\/\/doi.org\/10.1016\/j.tcs.2015.05.046 . From Computer Science to Biology and Back","DOI":"10.1016\/j.tcs.2015.05.046"},{"issue":"1\u20134","key":"10037_CR15","first-page":"263","volume":"75","author":"A Ehrenfeucht","year":"2007","unstructured":"Ehrenfeucht A, Rozenberg G (2007) Reaction systems. Fundam Informaticae 75(1\u20134):263\u2013280","journal-title":"Fundam Informaticae"},{"key":"10037_CR35","unstructured":"elementary set theory - Collection of all finite sets - Mathematics stack exchange. https:\/\/math.stackexchange.com\/a\/896291. [Online; accessed 2025-03-10]"},{"issue":"1","key":"10037_CR16","first-page":"51","volume":"12","author":"R Freund","year":"2016","unstructured":"Freund R, Ivanov S, Staiger L (2016) Going beyond turing with P automata: regular observer $$\\omega$$-languages and partial adult halting. Int J Unconv Comput 12(1):51\u201369","journal-title":"Int J Unconv Comput"},{"key":"10037_CR17","unstructured":"Glade N (2022) Le Vivant Rare, Faible et Amorphe - \u00c9volution Depuis les Origines Jusqu\u2019\u00e0 la Vie Telle Qu\u2019elle Nous Appara\u00eet. (Rare, Weak and Amorphous Life - evolution of life from the origins until life as it appears nowadays). Habilitation thesis (HDR), Grenoble. https:\/\/tel.archives-ouvertes.fr\/tel-04075075"},{"issue":"4","key":"10037_CR18","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/S41965-020-00055-X","volume":"2","author":"S Ivanov","year":"2020","unstructured":"Ivanov S, Petre I (2020) Controllability of reaction systems. J Membr Comput 2(4):290\u2013302. https:\/\/doi.org\/10.1007\/S41965-020-00055-X","journal-title":"J Membr Comput"},{"issue":"2","key":"10037_CR19","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/1008328.1008329","volume":"8","author":"DE Knuth","year":"1976","unstructured":"Knuth DE (1976) Big omicron and big omega and big theta. SIGACT News 8(2):18\u201324. https:\/\/doi.org\/10.1145\/1008328.1008329","journal-title":"SIGACT News"},{"key":"10037_CR20","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.68.051910","volume":"68","author":"J Lidmar","year":"2003","unstructured":"Lidmar J, Mirny L, Nelson DR (2003) Virus shapes and buckling transitions in spherical shells. Phys Rev E 68:051910. https:\/\/doi.org\/10.1103\/PhysRevE.68.051910","journal-title":"Phys Rev E"},{"key":"10037_CR21","doi-asserted-by":"publisher","first-page":"289","DOI":"10.3233\/FI-2017-1567","volume":"154","author":"A M\u0229ski","year":"2017","unstructured":"M\u0229ski A, Koutny M, Penczek W (2017) Verification of linear-time temporal properties for reaction systems with discrete concentrations. Fund Inform 154:289\u2013306. https:\/\/doi.org\/10.3233\/FI-2017-1567","journal-title":"Fund Inform"},{"key":"10037_CR22","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.ins.2015.03.048","volume":"313","author":"A M\u0229ski","year":"2015","unstructured":"M\u0229ski A, Penczek W, Rozenberg G (2015) Model checking temporal properties of reaction systems. Inf Sci 313:22\u201342. https:\/\/doi.org\/10.1016\/j.ins.2015.03.048","journal-title":"Inf Sci"},{"issue":"3","key":"10037_CR23","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1002\/j.1538-7305.1962.tb00480.x","volume":"41","author":"T Rad\u00f3","year":"1962","unstructured":"Rad\u00f3 T (1962) On non-computable functions. Bell Syst Tech J 41(3):877\u2013884","journal-title":"Bell Syst Tech J"},{"key":"10037_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5","volume-title":"Handbook of formal languages","year":"1997","unstructured":"Rozenberg G, Salomaa A (eds) (1997) Handbook of formal languages, vol 1\u20133. Springer, Berlin Heidelberg. https:\/\/doi.org\/10.1007\/978-3-642-59136-5"},{"key":"10037_CR25","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/J.TCS.2012.07.022","volume":"466","author":"A Salomaa","year":"2012","unstructured":"Salomaa A (2012) Functions and sequences generated by reaction systems. Theor Comput Sci 466:87\u201396. https:\/\/doi.org\/10.1016\/J.TCS.2012.07.022","journal-title":"Theor Comput Sci"},{"issue":"1","key":"10037_CR26","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1142\/S0129054113500044","volume":"24","author":"A Salomaa","year":"2013","unstructured":"Salomaa A (2013) Functional constructions between reaction systems and propositional logic. Int J Found Comput Sci 24(1):147\u2013160. https:\/\/doi.org\/10.1142\/S0129054113500044","journal-title":"Int J Found Comput Sci"},{"issue":"2","key":"10037_CR27","doi-asserted-by":"publisher","first-page":"247","DOI":"10.14232\/actacyb.22.2.2015.2","volume":"22","author":"A Salomaa","year":"2015","unstructured":"Salomaa A (2015) Two-step simulations of reaction systems by minimal ones. Acta Cybern 22(2):247\u2013257. https:\/\/doi.org\/10.14232\/actacyb.22.2.2015.2","journal-title":"Acta Cybern"},{"key":"10037_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1007\/978-3-319-13350-8_32","volume-title":"Computing with New Resources - Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday","author":"A Salomaa","year":"2014","unstructured":"Salomaa A (2014) Minimal reaction systems defining subset functions. In: Calude CS, Freivalds R, Iwama K (eds) Computing with New Resources - Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday, vol 8808. Lecture Notes in Computer Science. Springer, Cham, pp 436\u2013446. https:\/\/doi.org\/10.1007\/978-3-319-13350-8_32"},{"key":"10037_CR29","doi-asserted-by":"publisher","unstructured":"Segretain R, Trilling L, Glade N, Ivanov S (2021) Who plays complex music? On the correlations between structural and behavioral complexity measures in sign Boolean networks. In: 21st IEEE international conference on bioinformatics and bioengineering, BIBE 2021, Kragujevac, Serbia, October 25-27, 2021, pp. 1\u20136. IEEE, New York. https:\/\/doi.org\/10.1109\/BIBE52308.2021.9635403","DOI":"10.1109\/BIBE52308.2021.9635403"},{"key":"10037_CR30","doi-asserted-by":"publisher","unstructured":"St\u00e9rin T, Woods D (2024) Hardness of busy beaver value BB(15). In: Kov\u00e1cs, L., Sokolova, A. (eds.) Reachability Problems - 18th International Conference, RP 2024, Vienna, Austria, September 25-27, 2024, Proceedings. Lecture Notes in Computer Science, vol. 15050, pp. 120\u2013137. Springer, Cham. https:\/\/doi.org\/10.1007\/978-3-031-72621-7_9","DOI":"10.1007\/978-3-031-72621-7_9"},{"key":"10037_CR31","unstructured":"The reaction systems webpage. https:\/\/www.reactionsystems.org\/. [Online; accessed 2025-02-13]"},{"key":"10037_CR32","unstructured":"The busy beaver challenge. https:\/\/bbchallenge.org\/. [Online; accessed 2025-02-13] (2024)"},{"key":"10037_CR33","unstructured":"Wikipedia contributors: big O notation \u2014 Wikipedia, The Free Encyclopedia. https:\/\/en.wikipedia.org\/w\/index.php?title=Big_O_notation&oldid=1282096187. [Online; accessed 24-March-2025] (2025)"},{"key":"10037_CR34","unstructured":"Wikipedia contributors: Polynomial hierarchy \u2014 Wikipedia, The Free Encyclopedia. https:\/\/en.wikipedia.org\/w\/index.php?title=Polynomial_hierarchy&oldid=1279707173. [Online; accessed 26-March-2025] (2025)"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-025-10037-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11047-025-10037-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-025-10037-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T18:44:00Z","timestamp":1765219440000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11047-025-10037-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,4]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["10037"],"URL":"https:\/\/doi.org\/10.1007\/s11047-025-10037-6","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"value":"1567-7818","type":"print"},{"value":"1572-9796","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,4]]},"assertion":[{"value":"25 June 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 August 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}