The busy beaver game for reaction systems

Abstract The busy beaver game was introduced by Tibor Radó 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 . The function $$\text {BB}(n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>BB</mml:mtext> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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—a 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.