# The busy beaver game for reaction systems

Artiom Alhazov, Rudolf Freund, Sergiu Ivanov, Sergey Verlan

► To cite this version:

Artiom Alhazov, Rudolf Freund, Sergiu Ivanov, Sergey Verlan. The busy beaver game for reaction systems. Natural Computing, 2025, 24, pp.1013-1027. 10.1007/s11047-025-10037-6. hal-05205514

HAL Id: hal-05205514

https://univ-evry.hal.science/hal-05205514v1

Submitted on 6 Oct 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The busy beaver game for reaction systems

Artiom Alhazov<fnref n="1" /> · Rudolf Freund<fnref n="2" /> · Sergiu Ivanov<fnref n="3" /> · Sergey Verlan<fnref n="4" />

Accepted: 25 June 2025

© The Author(s) 2025

## 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 $BB(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—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.

**Keywords** Reaction systems · Busy beaver game · Theoretical biology

## 1 Introduction

Reaction systems are an abstract model of computing inspired by biochemical pathways (Brijder et al. 2011; Ehrenfeucht and Rozenberg 2007). The central object in reaction systems is the reaction, defined as a triple of sets: the set of reactants *R*, the set of inhibitors *I*, and the set of products *P*. A reaction is enabled in a given set of species

*W* if all reactants in *R* appear in *W* and none of the inhibitors in *I* appear in *W*. The result of applying such a reaction to *W* is simply the set of products *P*, meaning that all species appearing in *W*, but which are not reproduced by the reaction, vanish. In reaction systems this is known as the *non-permanency principle*. Furthermore, since the reactions and states are sets of species, reaction systems are a fundamentally qualitative model of computing—the species are not counted. The seminal paper (Ehrenfeucht and Rozenberg 2007) refers to this quality as the *threshold principle*: a species is either absent from the system, or available in “amounts” sufficient to satisfy any demand.

Research on reaction systems has always featured a prominent focus on their mathematical and computational properties. In particular, the complexity of their dynamics—cycles, periodicity, etc.—has been extensively studied (Dennunzio et al. 2015a, b, 2019). Works like (Męski et al. 2015; Azimi et al. 2015, 2016; Męski et al. 2017; Ivanov and Petre 2020) treat reaction systems as a formal modelling framework and study different aspects of model checking and controllability. In Salomaa (2012, 2013, 2014, 2015), reaction systems are seen as devices defining functions on sets of species, and the properties of these functions are investigated. In Alhazov et al. (2016, 2024), the connections between reaction systems and other formal models of computing are considered. We refer to The Reaction Systems Webpage (https://www.reactionsystems.org/) for further references.

<figure><img src="image_2.png" /></figure>

<footnote>Artiom Alhazov, Rudolf Freund, Sergiu Ivanov and Sergey Verlan have contributed equally to this work.</footnote>

<footnote>Sergiu Ivanov
sergiu.ivanov@universite-paris-saclay.fr</footnote>

<footnote>Artiom Alhazov
artiom@math.md</footnote>

<footnote>Rudolf Freund
rudi@emcc.at</footnote>

<footnote>Sergey Verlan
verlan@u-pec.fr</footnote>

<footnote n="1">¹ State University of Moldova, Vladimir Andrunachievici Institute of Mathematics and Computer Science, Academiei 5, MD-2028 Chiinău, Moldova</footnote>

<footnote n="2">² Faculty of Informatics, TU Wien, Favoritenstraße 9–11, 1040 Wien, Austria</footnote>

<footnote n="3">³ IBISC, Univ. Évry, Paris-Saclay University, 23, boulevard de France, 91034 Évry, France</footnote>

<footnote n="4">⁴ LACL, Univ. Paris Est Créteil, 61, av. Général de Gaulle, 94010 Créteil, France</footnote>
In this paper, we aim to contribute to the study of computational properties of reaction systems by focusing on the busy beaver game in reaction systems. The busy beaver game was originally introduced for Turing machines in Radó (1962) and, in its classical form, consists in constructing deterministic halting machines with a binary alphabet and a fixed number of states *n*, and picking out the longest run performed by such a machine. The number of steps in such a longest run is denoted $BB(n)$. A generalization to alphabets containing more than 2 symbols was proposed in Brady (1988). Most recently, the value of $BB(5)$ was settled at 47,176,870 (The Busy Beaver Challenge 2024), and it was proved that “knowing $BB(15)$ is at least as hard as solving [a] Collatz-related conjecture” (Stérin and Woods 2024).

Seen as a model of computing, reaction systems are quite different from Turing machines. A state of a reaction system is a subset of a finite set, so the state space is always finite. Their dynamics are fueled by context sequences, potentially adding new input to every state. Reaction systems have no halting: the length of the context sequence determines the length of a run. Finally, the result of applying the reactions is fully deterministic, which together with the finiteness of the state space means that the dynamics is necessarily a cycle, possible preceded by a finite aperiodic sequence of states—a preperiod (Dennunzio et al. 2015b). The computational power of reaction systems has been shown to be equivalent to that of Boolean functions (Brijder et al. 2011), and therefore indirectly to that of finite automata.

Thinking of the busy beaver game in the context of reaction systems is consequently very different from thinking about it in the original setting for Turing machines. The function $BB(n)$ is known to be uncomputable, while in reaction systems the length of a longest run is bounded by a natural number—$2^{|S|}$, where *S* is the set of species. This difference is in fact a strong motivation for considering optimization targets other than the length of the run, and may lead to an interesting shift of the point of view on the notion and the meaning of a busy beaver champion.

In this paper, we introduce a general framework for the busy beaver game in reaction systems, and we then propose and study several concrete variants. Our framework focuses on observing some non-local features of the behavior—somewhat in the spirit of observer languages in P systems and other models of computing (Freund et al. 2016; Cavaliere et al. 2007)—and measuring a form of time distance on these observations.

Besides translating the busy beaver challenge to reaction systems, we have the following two major goals in mind when proposing our general framework:

1. *Formal generalization:* Generalize the formulation of the busy beaver game, allowing for multiple new variants, some of which can potentially be further exported to other models of computing, like P systems, register machines, Boolean networks, etc.

2. *Framework for origins of life:* The original busy beaver game can be interpreted as a longevity-based competition: given a fixed amount of resources, which “individual” can sustain an activity the longest? The generalized formulation we propose in this paper allows for defining other competition criteria, which we expect to be useful in thinking about some aspects of the biological evolution.<fnref n="1" />

This paper is structured as follows. In Sect. 2 we recall the necessary notions of reaction systems, as well as give some brief general background. In Sect. 3 we introduce the busy beaver frames—a formalization of the idea of measuring the distance between subsequent observations of a feature. Then in Sect. 4 we introduce the generalized beaver game based on busy beaver frames, and give several concrete instantiations of the generalized framework, focusing on longest runs, periods, preperiods, etc. In Sect. 5 we discuss the busy beaver challenge for the size function measuring the cardinality of the background set of the reaction system, and then in Sect. 6 we discuss the size function measuring the size of the set of reactions. Section 7 summarizes the work and draws conclusions. In Sect. 8 we discuss the potential applications and implications of the busy beaver game for some questions in theoretical biology. Finally, Sect. 9 gives major directions for potential future work.

## 2 Preliminaries

In this section we briefly recall the notions of reaction systems and formal language theory necessary for reading this paper. For a more extensive introduction and overviews we refer to Rozenberg and Salomaa (1997); Brijder et al. (2011); The Reaction Systems Webpage https://www.reactionsystems.org/.

### 2.1 General background

Given a set $A$ and a subset $B \subseteq A$, the corresponding indicator function (also known as the characteristic function) of $i_B: A \to \{0, 1\}$ is defined as $i_B(a) = 1$ if $a \in B$ and $i_B(a) = 0$ otherwise. In this paper, we will sometimes use the subset $B$ and the indicator function $i_B$ interchangeably.

<footnote n="1">¹ This line of thinking is strongly connected with the approach based on P systems in Alhazov et al. (2024).</footnote>
A relation $\leq \subseteq A \times A$ is called a partial order if it satisfies the following 3 conditions:

1. *reflexivity*: $a \leq a$ for all $a \in A$,

2. *antisymmetry*: if $a \leq b$ and $b \leq a$, then $a = b$, for all $a, b \in A$,

3. *transitivity*: if $a \leq b$ and $b \leq c$, then $a \leq c$.

For a finite set $A$, $A^*$ denotes the set of all finite sequences (words) over $A$. We will use parentheses $(a_1, ..., a_l)$ or simple concatenation $a_1...a_l$ to denote these sequences, depending on the context. For such a sequence $\alpha = a_1...a_l$ we will denote the length of the sequence $|\alpha| = l$.

Given a function $f: A \times B \rightarrow C$, and an element $a \in A$, we will denote by $f(a)$ the function $f(a) : B \rightarrow C$ with the property $f(a)(b) = f(a, b)$, for all $b \in B$.<fnref n="2" />

## 2.2 Reaction systems

Given a finite set $S$—called the background set of species—a reaction in $S$ is a triple $a : (R_a, I_a, P_a)$, with $R_a, I_a, P_a \subseteq S$, and $R_a \cap I_a = \emptyset$. The subsets of species $R_a, I_a$, and $P_a$ are called the reactants, the inhibitors, and the products of reaction $a$.

Given a subset of species $W \subseteq S$, reaction $a$ is said to be enabled in $W$ if $R_a \subseteq W$ and $I_a \cap W = \emptyset$. The result of $a$ on $W$ is denoted by $\mathbf{res}_a(W)$ and is equal to the set of products of $a$: $\mathbf{res}_a(W) = P_a$. Given a set of reactions $A$, all of which are enabled in $W$, the result of $A$ is $\mathbf{res}_A(W) = \bigcup_{a \in A} \mathbf{res}_a(W) = \bigcup_{a \in A} P_a$. A reaction system over the background set $S$ is a tuple $\mathcal{A} = (S, A)$, where $A$ is a set of reactions in $S$. The result of $\mathcal{A}$ on $W$ is defined as the result of all its reactions: $\mathbf{res}_A(W) = \mathbf{res}_A(W)$. A state of a reaction system $\mathcal{A} = (S, A)$ over the background set of species $S$ is any subset of species $W \subseteq S$. A state $W$ is reachable by $\mathcal{A}$ if there exists another state $V \subseteq S$ such that $\mathbf{res}_A(V) = W$.

The dynamics of reaction systems are defined to be open in the sense that they may receive external input at every step. More formally, consider the following sequence of subsets of species, called the context sequence $\gamma = (C_i)_{0 \leq i \leq n}$, $C_i \subseteq S$, $n \in \mathbb{N}$. The interactive process in $\mathcal{A}$ driven by $\gamma$ is defined as the pair $\pi_\gamma(\mathcal{A}) = (\delta_\gamma(\mathcal{A}), \tau_\gamma(\mathcal{A}))$, where

* $\delta_\gamma(\mathcal{A}) = (D_i)_{0 \leq i \leq n}$ is the result sequence: $D_i = \mathbf{res}_\mathcal{A}(D_{i-1} \cup C_{i-1})$ for $0 < i \leq n$, and $D_0 = \emptyset$,

* $\tau_\gamma(\mathcal{A}) = (W_i)_{0 \leq i \leq n}$ is the state sequence: $W_i = C_i \cup D_i$.

Each element $D_i$ of $\delta_\gamma(\mathcal{A})$ is computed as the result of $\mathcal{A}$ on the previous state $W_{i-1}$, and each state is computed as the

union between the result of $\mathcal{A}$ and the corresponding element of the context sequence. $C_0$ is the called the initial context of $\pi_\gamma(\mathcal{A})$, $W_0$ is called its initial state, and $W_n$ is called the result of $\mathcal{A}$ along the context sequence $\gamma$, and is denoted by $\mathbf{res}_A^\gamma(W_0) = W_n$. If $C_i \subseteq D_i$ for every $0 < i \leq n$, then the corresponding interactive process $\pi_\gamma(\mathcal{A})$ is called context-independent<fnref n="3" />. A state $W$ is called reachable from state $V$ if there exists a context sequence $\gamma$ such that $W = \mathbf{res}_A^\gamma(V)$.

**Example 1** Consider the reaction system $\mathcal{A} = (S, A)$, where $S = \{x, y, z\}$ and $A = \{a_1 : \{(x), \{y\}, \{z\}\}, a_2 : \{(y), \{x\}, \{z\}\} \}$. Reaction $a_1$ is enabled in $\{x\}$, but not in $\{x, y\}$ or $\emptyset$. The result of $a_1$ on $\{x\}$ is $\mathbf{res}_{a_1}(\{x\}) = \{z\}$. The result of $A$ on $\{x\}$ is $\mathbf{res}_A(\{x\}) = \{z\}$ again, because $a_2$ is not enabled in $\{x\}$.

Consider the context sequence $\gamma = (C_0 = \{x\}, C_1 = \{y\}, C_2 = \emptyset)$. The interactive process $\pi_\gamma(\mathcal{A})$ consists of the following sequences:

* result sequence: $\delta_\gamma(\mathcal{A}) = (D_0 = \emptyset, D_1 = \{z\}, D_2 = \{z\})$;

* state sequence: $\tau_\gamma(\mathcal{A}) = (W_0 = \{x\}, W_1 = \{y, z\}, W_2 = \{z\})$.

Therefore, $\{z\}$ is reachable from $\{x\}$ as there exists the context sequence $\gamma$ driving $\mathcal{A}$ from $\{x\}$ to $\{z\}$.

**Remark 1** In Brijder et al. (2011), the reactant and the inhibitor sets of a reaction are required to be nonempty, while the seminal paper (Ehrenfeucht and Rozenberg 2007) does not explicitly state this requirement. Later works have studied the influence of this restriction on different aspects ranging from expressive power to modelling, e.g., Azimi et al. (2014); Salomaa (2015, 2014); Dennunzio et al. (2019, 2015b, 2015a); Azimi et al. (2016, 2015). In this paper, we explicitly discuss the impact of the nonemptiness requirement on the busy beaver game.

## 3 Busy beaver frames

In this section we introduce a general structure for expressing some non-local properties over interactive processes of reaction systems. Informally, this structure is organized in two levels:

1. a non-local observer function $\varphi$ indicating a target property on a sequence of states of an interactive process, and

<footnote n="2">² Applying $f$ to one of its arguments in this way is typically known as *currying*.</footnote>

<footnote n="3">³ Intuitively, the contexts in the context-independent interactive process $\pi_\gamma(\mathcal{A})$ do not inject any new species. This means that an equivalent interactive process can be obtained by setting all $C_i$ to $\emptyset$, for $i > 0$.</footnote>
2. a mass function $m$ producing a measurement for the interactive process on which $\varphi$ observes the target property.

All definitions in this section will be given with respect to a fixed reaction system $\mathcal{A} = (S, A)$.

**Definition 1** An order $k$ observer function is any computable function $\varphi : (2^S)^* \times \mathbb{N}^k \to \{0, 1\}$ such that for any two sequences of states $\alpha = (W_0, \dots, W_l)$ and $\beta = (V_0, \dots, V_m)$, $\alpha, \beta \in (2^S)^*$, and any vector $\mathbf{i} = (i_1, \dots, i_k) \in \mathbb{N}^k$, the following holds: if $W_{i_j} = V_{i_j}$ for all $1 \le j \le k$, then $\varphi(\alpha, \mathbf{i}) = \varphi(\beta, \mathbf{i})$.

Intuitively, an observer function acts on a sequence of states $\alpha \in (2^S)^*$ and a length $k$ sequence of indices into $\alpha$, and is equal to 1 if and only if the sequence $\alpha$ has some target property. The observer function is additionally constrained to only depend on the states indexed in the vector $\mathbf{i}$. In the situations in which the sequence $\alpha$ is shorter than some of the indices appearing in $\mathbf{i}$, we fix $\varphi(\alpha, i) = 0$.

**Example 2** Consider a sequence of states $\alpha = (W_0, \dots, W_l)$ and the order 2 observer function $\varphi_{\text{rpt}} : (2^S)^* \times \mathbb{N}^2 \to \{0, 1\}$ defined as follows: $\varphi_{\text{rpt}}(\alpha, i, j) = 1$ iff $i < j \le l$ and $W_i = W_j$ ($\varphi_{\text{rpt}}(\alpha, i, j) = 0$ in all other cases). Then $\varphi_{\text{rpt}}$ equals 1 only for sequences in which a state is repeated in positions $i$ and $j$.

The function $\varphi_{\text{rpt}}(\alpha) : \mathbb{N}^2 \to \{0, 1\}$ is essentially an indicator function defining the subset of $\{(i, j) \mid \varphi_{\text{rpt}}(\alpha, i, j) = 1\} \subseteq \mathbb{N}^2$. We will use the same notation $\varphi_{\text{rpt}}(\alpha)$ to refer to this subset. Note that $\varphi_{\text{rpt}}(\alpha) \neq \emptyset$ iff some states are repeated in $\alpha$.

**Definition 2** An order $k$ mass function is any computable function $m : \mathbb{N}^k \to (M, \leq)$, where $(M, \leq)$ is a set equipped with a partial order relation.

For readability, we may omit spelling out the symbol for the partial order relation, i.e., we may write simply $M$ instead of $(M, \leq)$ when the partial order relation $\leq$ is clear from the context.

**Example 3** Let $\leq$ be the lexicographical ordering on vectors of integer numbers $\mathbb{Z}$ and consider the order $k$ mass function $m_{\text{len}}^k : \mathbb{N}^k \to (\mathbb{Z}^{k-1}, \leq)$ defined as follows:

$$m_{\text{len}}^k(i_1, i_2, i_3, \dots, i_{k-1}, i_k) = (i_2 - i_1, i_3 - i_2, \dots, i_k - i_{k-1}).$$

Thus, for an ordered vector $\mathbf{i} = (i_1, \dots, i_k)$, $m_{\text{len}}^k(\mathbf{i})$ is the vector of distances between the values in $\mathbf{i}$.

Let $\mathcal{A}$ denote the class of all reaction systems,<fnref n="4" /> and consider the computable mapping $\text{size} : \mathcal{A} \to \mathbb{N}^d$, $d \in \mathbb{N}$, assigning a $d$-vector of natural numbers to every reaction

system which we will call size. For such a vector $\mathbf{n} \in \mathbb{N}^d$, we denote by $\mathcal{RS}(\mathbf{n})$ the class of reaction systems of size $\mathbf{n}$: $\mathcal{RS}(\mathbf{n}) = \{\mathcal{A} \in \mathcal{A} \mid \text{size}(\mathcal{A}) = \mathbf{n}\}$. When $d = 1$, $\mathbf{n}$ is just a natural number, so we will use the non-boldface notations $n$ and $\mathcal{RS}(n)$.

**Example 4** Multiple aspects of a reaction system can be considered in measuring its size. In this paper we will only consider measures of descriptional complexity computable in polynomial or even linear time, e.g.:

* The size of the background set $|\mathcal{S}|$,

* The number of reactions $|\mathcal{A}|$,

* The maximal size of a component of reaction $\max_{a \in \mathcal{A}} \{|R_a|, |I_a|, |P_a|\}$, etc.

Any combination of the above can also be seen as an example of a size function.

Having $d > 1$ may be useful to explicitly measure or limit the sizes of the individual components of reactions,<fnref n="5" /> e.g., the following 3-vector can also be seen as a size of a reaction system $\mathcal{A}$: $(\max_R, \max_I, \max_P)$, where $\max_X = \max_{a \in \mathcal{A}} |X_a|$, and $X \in \{R, I, P\}$.

**Definition 3** Given a finite set $S$, two numbers $k, d \in \mathbb{N}$, a busy beaver frame is the tuple $\mathcal{F} = (\varphi, m, M, \text{size}, \mathbf{n})$, where

* $\varphi : (2^S)^* \times \mathbb{N}^k \to \{0, 1\}$ is an order $k$ observer function (Definition 1),

* $m : \mathbb{N}^k \to (M, \leq)$ is an order $k$ mass function (Definition 2),

* $M = (M, \leq)$ is a partially ordered set,

* $\text{size} : \mathcal{A} \to \mathbb{N}^d$ is a size function,

* $\mathbf{n} \in \mathbb{N}^d$ is the target size of considered reaction systems.

Intuitively, a busy beaver frame fixes the ingredients needed for defining the busy beaver game: the property to observe ($\varphi$), a way to produce measures on the corresponding interactive processes ($m$), a way to compare these measures (($M, \leq$)), a way to measure the size of reaction systems ($\text{size}$) as well as the size of the reaction systems to be considered ($n$). Figure 1 gives a graphical intuition for how a busy beaver frame operates for order 2 observer and mass functions.

<footnote n="4">⁴ In set theory terms, the collection of all reaction systems cannot be a set, since multiple reaction systems can be defined for any given finite set considered as a background set, and since the collection of all finite sets is not a set, see (Elementary set theory https://math.stackexchange.com/a/896291.) for a short non-peer-reviewed proof. We therefore use the term *class of all reaction systems* and design our definitions in a way that does not assume set-like characteristics of $\mathcal{A}$.</footnote>

<footnote n="5">⁵ This is typically how rule size is measured in insertion-deletion systems, in which a rule is given by a triple of strings (Alhazov et al. 2024).</footnote>
<figure><img src="image_3.png" /><figcaption>**Fig. 1** A graphical illustration of a busy beaver frame with an order 2 observer function $\varphi$ and an order 2 mass function $m$. The first line is the length $l$ seed context sequence $\sigma_l(C_0)$ starting with the initial context $C_0$ (Definition 4). The second line shows the state sequence (Sect. 2.2) of the interactive process $\pi$ driven by $\sigma_l(C_0)$. The states $W_i$ and $W_j$ are highlighted because $\varphi(\pi, i, j) = 1$, or equivalently</figcaption></figure>

$(i,j) \in \varphi(\pi)$. $m(i, j)$ is illustrated as a distance between steps $i$ and $j$ of $\pi$, not necessarily equal to $j - i$. The generalized busy beaver game for reaction systems (Sect. 4.2) essentially consists in optimizing the values of the mass function $m$

We assume by default the class of all reaction systems, but busy beaver frames over more restricted categories can be considered, e.g., the set of all reaction systems in which none of the reactant or inhibitor sets are empty. We will refer to this restricted class of reaction systems by the symbol $A_{-\emptyset}$. When discussing busy beaver frames over a restricted class of reaction systems $A' \subseteq A$, we will write it in the superscript $\mathcal{F}^{A'}$.

# 4 Generalized busy beaver game

In this section we use the busy beaver frame to build a generalization of the busy beaver game for reaction systems.

## 4.1 Seeds and interactive processes

As noted in Sect. 2.2, the dynamics of reaction systems are interactive processes driven by context sequences, potentially injecting additional input at every step. On the other hand, the original formulation of the busy beaver game supposes starting with a certain fixed input and examining the longest runs receiving no additional contribution later on. A natural way of representing this in reaction systems (also adopted in works like (Dennunzio et al. 2015b, 2019) and Salomaa (2015)) is considering a context sequence in which only the first context is non-empty. In this work, we will call such context sequences *seeds*.

As in Sect. 3, the definitions which follow are given with respect to a fixed reaction system $\mathcal{A} = (S, A)$.

**Definition 4** Given an initial context $C_0 \subseteq S$, the corresponding seed of length $l \in \mathbb{N}$, $l \ge 1$, is $\sigma_l(C_0) = (C_0, \emptyset, \dots, \emptyset)$ such that $|\sigma_l(C_0)| = l$. We write $\sigma(C_0) = \{\sigma_l(C_0) | l \in \mathbb{N}, l \ge 1\}$ to refer to the set of all seeds obtained from $C_0$, and $\sigma(\mathcal{A}) = \{\sigma(C_0) | C_0 \subseteq S\}$ to refer to the set of all seeds in the reaction system $\mathcal{A}$. We denote

$\text{sint}(\mathcal{A})$ the set of *seeded interactive processes* of the reaction system $\mathcal{A}$: $\text{sint}(\mathcal{A}) = \{\pi_{\gamma}(\mathcal{A}) | \gamma \in \sigma(\mathcal{A})\}$.

We explicitly remark that the set of all seeds $\sigma(C_0)$ is infinite for any initial context $C_0 \subseteq S$ because it contains context sequences with arbitrary-length suffixes of $\emptyset$. As a consequence, $\sigma(\mathcal{A})$ and $\text{sint}(\mathcal{A})$ are both infinite as well. Furthermore, $\text{sint}(\mathcal{A})$ contains exactly one interactive process for every seed in $\sigma(\mathcal{A})$.

**Remark 2** Restricting context sequences as strongly as to require them to have the form of a seed is not strictly speaking necessary to study the dynamics of reaction systems. A context sequence is indeed a word over the alphabet $2^S$, so in a more general setting one could consider specifying the family of languages from which the context sequences should come, e.g., regular languages over $2^S$. In this paper, we restrict the allowed context sequences to seeds mainly for the following two reasons:

1. Seeded interactive processes intuitively resemble Turing machine computations starting with a fixed input,

2. Seeded interactive processes make definitions of concrete busy beaver frames easier to use.

## 4.2 Generalized framework

The main idea behind the generalized framework for the busy beaver game is to identify a property on seeded interactive processes of reaction systems of a given size, and then optimize the value of the mass function for these interactive processes.

Let $\mathcal{F} = (\varphi, m, M, \text{size}, \mathbf{n})$ be a busy beaver frame (Sect. 3), where $\varphi$ is the observer function, $m$ is the mass function, $(M, \leq)$ is a partially ordered set, $\text{size}: A \to \mathbb{N}^d$ is a size function, and $\mathbf{n}$ is the target size of reaction systems. Recall that we denote by $\mathcal{RS}(\mathbf{n})$ the class of all reaction systems of size $\mathbf{n}$.
The generalized busy beaver game is defined by the computation of the following value, where $S_A$ is the background set of the reaction system $\mathcal{A}$:

$$ \mu_{\mathcal{F}} = \max_{\mathcal{A} \in \mathcal{RS}(\mathbf{n})} \max_{C_0 \subseteq S_A} \min_{\gamma \in \sigma(C_0)} \{m(\lambda) \mid \lambda \in \varphi(\pi_{\gamma})\}. \quad (1) $$

Before explaining the above formula in detail, we recall that $\varphi(\pi_{\gamma})$ can be seen as defining a subset of vectors in $\mathbb{N}^k$ having the target property (Sect. 3). Intuitively, for the interactive process $\pi_{\gamma}$ driven by the seed $\gamma$, the set $\{m(\lambda) \mid \lambda \in \varphi(\pi_{\gamma})\}$ implies considering all vectors of positions $\lambda$ at which the target property is observed, and then producing a measurement on each of these vectors via $m$.

The computation of the value $\mu_{\mathcal{F}}$ can be logically decomposed into the following three steps:

1. Given a reaction system $\mathcal{A}$ and an initial context $C_0$, consider all interactive processes driven by the seeds in $\sigma(C_0)$ having the target property, and take the smallest value of the mass function $m$:

$$ \mu_{\mathcal{F}}(\mathcal{A}, C_0) = \min_{\gamma \in \sigma(C_0)} \{m(\lambda) \mid \lambda \in \varphi(\pi_{\gamma})\}. $$

2. Given a reaction system $\mathcal{A}$, take the seed $C_0$ yielding the largest value of $\mu_{\mathcal{F}}(\mathcal{A}, C_0)$:

$$ \mu_{\mathcal{F}}(\mathcal{A}) = \max_{C_0 \subseteq S_A} \{\mu_{\mathcal{F}}(\mathcal{A}, C_0)\}. $$

3. Among all reaction systems $\mathcal{A} \in \mathcal{RS}(\mathbf{n})$, take the largest value of $\mu_{\mathcal{F}}(\mathcal{A})$:

$$ \mu_{\mathcal{F}} = \max_{\mathcal{A} \in \mathcal{RS}(\mathbf{n})} \mu_{\mathcal{F}}(\mathcal{A}). $$

The intuitive reason for including a min operation in step 1 is essentially to help deal with the fact that reaction systems do not have a halting condition, and will become clearer with concrete examples in the next section.

**Remark 3** (Existence of the extrema) The minimum denoted as $\mu_{\mathcal{F}}(\mathcal{A}, C_0)$ in Eq. (1) need not always exist for a fixed context $C_0$, e.g., when the set $\{m(\lambda) \mid \lambda \in \varphi(\pi_{\gamma})\}$ has no minimal element, or simply when $\varphi(\pi_{\gamma}) = \emptyset$. We will therefore consider that the maximum $\mu_{\mathcal{F}}(\mathcal{A})$ implicitly discards the initial contexts $C_0$ for which the minimum $\mu_{\mathcal{F}}(\mathcal{A}, C_0)$ does not exist. In its own turn, the maximum $\mu_{\mathcal{F}}(\mathcal{A})$ need not always exist either, in which case we consider that the leftmost maximum $\mu_{\mathcal{F}}$ implicitly discards the reaction systems $\mathcal{A}$ for which the maximum $\mu_{\mathcal{F}}(\mathcal{A})$ does not exist. Finally, the leftmost maximum $\mu_{\mathcal{F}}$ may not exist, in which case we conclude that such a generalized beaver game frame $\mathcal{F}$ has no champion.

Implicitly discarding situations in which the extrema in equation (1) do not exist follows the spirit of the original busy beaver game, in which only the halting runs of a

Turing machine are considered, and the non-halting ones for which the notion of the length is undefined are therefore discarded.

As discussed in Sect. 3, generalized busy beaver games can also be considered over restrictions of $\mathcal{A}$, e.g., the class of reaction systems $\mathcal{A}_{-\emptyset}$ with non-empty reactant and inhibitor sets. When dealing with a restricted class $\mathcal{A}' \subseteq \mathcal{A}$, we will indicate $\mathcal{A}'$ as a superscript to the busy beaver frame: $\mu_{\mathcal{F}}^{\mathcal{A}'}$.

## 4.3 Concrete busy beaver games

We will now give several concrete instantiations of the generalized framework introduced above.

### 4.3.1 Longest runs

The first instantiation aims at directly translating the notion of a longest run from the original definition for Turing machines. Reaction systems do not have a halting condition and the length of interactive processes is given by the length of the context sequence, but one may consider that the end of an interactive process is its first empty state $W_j = \emptyset$, for some $j > 0^6$. With this approach in mind, we can define a busy beaver frame focused on longest runs in the following way:

$$ \mathcal{F}_{lr}(\mathbf{size}, \mathbf{n}) = (\varphi_{lr}, m_{len}^2, \mathbb{Z}, \mathbf{size}, \mathbf{n}), \text{ where} $$

$$ \varphi_{lr}(\pi, i, j) = \begin{cases} 1, & i = 0 < j \text{ and } W_j = \emptyset, \\ 0, & \text{otherwise.} \end{cases} $$

Thus, $\varphi_{lr}(\pi, i, j) = 1$ when $i$ is the first state of the interactive process, and $j$ is an empty state. The mass function $m_{len}^2$ is defined as in Example 3, $m_{len}^2(i, j) = j - i$. For this frame, the effect of equation (1) is as follows:

1. for a reaction system $\mathcal{A}$ and a context $C_0 \subseteq S_A$, $\mu_{\mathcal{F}}(\mathcal{A}, C_0)$ will correspond to the shortest time it takes $\mathcal{A}$ to get from $C_0$ to the empty set;

2. for a reaction system $\mathcal{A}$, $\mu_{\mathcal{F}}(\mathcal{A})$ will correspond to the context yielding the longest shortest time to reach the empty set;

3. $\mu_{\mathcal{F}}$ will correspond to the reaction system $\mathcal{A} \subseteq \mathcal{RS}(\mathbf{n})$ having the largest $\mu_{\mathcal{F}}(\mathcal{A})$.

**Remark 4** The translation of the idea of the longest run to a halting state to a reaction system reaction reaching an empty state $W_i = \emptyset$ is of limited fidelity, in particular for reaction systems $\mathcal{A}$ with the property that $\mathrm{res}_{\mathcal{A}}(\emptyset) \neq \emptyset$. In such cases, our definition of the busy beaver game—

<footnote n="6">6 Additional motivation comes from the fact that we are considering seeded interactive processes, in which only the first context is non-empty.</footnote>
$\mu_F(\mathcal{A}, C_0)$ in particular—simply measures the time to the first empty state, which may not necessarily be seen as a “halting state”. Our conclusion from this observation is that different busy beaver frames are possibly more appropriate for reaction systems.

**Remark 5** As follows from the definitions in Sect. 2.2, reaction systems are deterministic in the sense that any one context sequence $\gamma$ always yields the same interactive process $\pi_\gamma$. Considering the set of all seeds $\sigma(C_0)$ starting with the same initial context $C_0$ can therefore be seen as “simulating” unbounded computation on the same input, while the interactive processes $\pi_\sigma$, $\sigma \in \sigma(C_0)$, can be seen as “samples” of the behavior of the reaction system seeded by the initial context $C_0$. From this point of view, the min operation in the computation of $\mu_F(\mathcal{A}, C_0)$ can be interpreted as pointing at the first time the target feature is observed when starting from a fixed initial context.<fnref n="7" />

### 4.3.2 Longest periods

Since reaction systems are deterministic (Remark 4), their behavior necessarily ends in a cyclic attractor—a period— or a fixed point (e.g., Dennunzio et al. (2015b)). From this point of view, it is natural to consider the busy beaver frame focused on obtaining the longest period:

$$ \mathcal{F}_{per}(\mathbf{size}, \mathbf{n}) = (\varphi_{rpt}, m_{len}^2, \mathbb{Z}, \mathbf{size}, \mathbf{n}), $$

where $\varphi_{rpt}$ is defined as in Example 2: $\varphi_{rpt}(\pi, i, j) = 1$ if and only if the states are repeated at positions $i$ and $j$ in $\pi$. Thus, computing $\mu_F(\mathcal{A}, C_0)$ will identify the shortest interval between repeated states, i.e., the length of the period in the behavior of $\mathcal{A}$ seeded by $C_0$. Respectively, computing $\mu_F(\mathcal{A})$ will identify the initial context leading to the longest period, and $\mu_F$ will identify the reaction system in $RS(n)$ having the longest period among all reaction systems of size $n$.

### 4.3.3 Longest preperiods

The dynamics of reaction systems consists of a period preceded by a bounded non-periodic prefix of states, to which we refer as the preperiod. Here is a way to set up a busy beaver frame focusing on the longest preperiods:

$$ \mathcal{F}_{pper}(\mathbf{size}, \mathbf{n}) = (\varphi_{pper}, m_{pper}, \mathbb{Z}, \mathbf{size}, \mathbf{n}), $$

where

$$ \begin{aligned} \varphi_{pper}(\pi, i, j, k) &= \begin{cases} 1, & i = 0 < j < k \text{ and } W_j = W_k, \\ 0, & \text{otherwise,} \end{cases} \\ m_{pper}(i, j, k) &= j. \end{aligned} $$

This time, the observer function $\varphi_{pper} : (2^S)^* \to \mathbb{N}^3$ and the mass function $m_{pper} : \mathbb{N}^3 \to \mathbb{Z}$ are both order 3, which allows on the one hand requiring a repetition of states ($W_j = W_k$) and on the other hand measuring the number of states preceding this repetition (since $i$ must be 0). In this frame, the value $\mu_F(\mathcal{A}, C_0)$ corresponds to finding the period (like in the case of $\varphi_{per}$), and the minimum condition ensures that the first such repetition is considered, as the distance $j - i = j$ is minimized. Finally, and similarly to the case of $\mathcal{F}_{per}$, subsequent computation of $\mu_F(\mathcal{A})$ and $\mu_F$ ensures that the longest preperiod is measured across all reaction systems of size $n$.

### 4.3.4 Further variants and remarks

The generalized framework for the busy beaver game in reaction systems can further be instantiated in multiple other forms. For example, instead of considering the equality restriction $W_i = W_j$ as in $\varphi_{per}$ and $\varphi_{pper}$, one could consider partial equality, for example by requiring that the size of the intersection $|W_i \cap W_j|$ be above a certain threshold.

In Sect. 4.3.1, we suggested translating the halting condition from Turing machines to the event of a reaction system reaching an empty state $\emptyset$, and we mentioned some shortcomings of this translation, related in particular to the fact that reaction systems do not have halting. A more appropriate translation could involve adult halting or even partial adult halting, as outlined for P systems in Freund et al. (2016). Intuitively, the adult halting condition corresponds to the fact that the system reaches a fixed point: nothing changes any more, the system has reached an “adult” state. Within our framework, we could imagine a frame measuring the longest run before reaching the fixed point based on the observer function $\mu_{pper}$. Indeed, it suffices to modify the conditions under which $\mu_{pper}$ is true to also require that the repeated states $W_j$ and $W_k$ be one step away, i.e., $k = j + 1$ or equivalently $W_k = \text{res}_A(W_j)$. In fact, the 3rd index $k$ is not even needed, so the frame can be defined as:

$$ \mathcal{F}_{apper}(\mathbf{size}, \mathbf{n}) = (\varphi_{apper}, m_{len}^2, \mathbb{Z}, \mathbf{size}, \mathbf{n}), $$

where

$$ \varphi_{apper}(\pi, i, j) = \begin{cases} 1, & i = 0, j > 1, \text{ and } W_{j-1} = W_j, \\ 0, & \text{otherwise.} \end{cases} $$

Remark that $\varphi_{apper}$ relies on the fact that, in any seeded interactive process, $\text{res}_A(W_{j-1}) = W_j$ implies that $W_k = W_j$ for all $k > j$. Further remark that the equality $W_{j-1} = W_j$ can once again be generalized to the sets $W_{j-1}$ and $W_j$ having an intersection of at least a certain size, or sharing a

<footnote n="7">⁷ This interpretation can be considerably influenced by the choice of the mass function $m$.</footnote>
fixed subset of species, somewhat similarly to mass conservation in Azimi et al. (2016) and partial adult halting (Freund et al. 2016), etc.

Finally, even though observer functions are designed to be non-local, the general framework allows (somewhat trivially) measuring the time between successive appearances of a local feature in the state, e.g., the presence of a certain species. Let $p: 2^S \to \{0, 1\}$ be a local predicate on states. Then the following frame measures the distance between consecutive observations of $p$:

$$ 
\begin{aligned}
\mathcal{F}_{\text{loc}}(\mathbf{size}, \mathbf{n}, p) &= (\varphi_{\text{loc}}(p), m_{\text{len}}^2, \mathbb{Z}, \mathbf{size}, \mathbf{n}), \text{ where} \\
\varphi_{\text{loc}}(p, \pi, i, j) &= \begin{cases} 1, & i<j, p(i) = 1, \text{ and } p(j) = 1, \\ 0, & \text{otherwise.} \end{cases}
\end{aligned}
$$

# 5 The busy beaver game for $size(\mathcal{A}) = |S_\mathcal{A}|$

In this section we provide some busy beaver champions for the concrete busy beaver games shown in Sect. 4.3, and using the size of the background set as the measure of size: $size(\mathcal{A}) = |S_\mathcal{A}|$. We start by discussing the case in which empty reactant and inhibitor sets are allowed.

## 5.1 Empty reactants and inhibitors allowed

The number of states a reaction system $\mathcal{A}$ can reach is bounded by the total number of subsets of its background set, i.e., $2^{|S_\mathcal{A}|}$, and multiple works starting with (Brijder et al. 2011) showed a reaction system which traverses all of these states: the binary counter. We give here a simple variant of this construction.

**Example 5** (Binary counter) Take an arbitrary $t \in \mathbb{N}$ and consider the reaction system $A_{01} = (S_{01}, A_{01})$ implementing the $t$-bit binary counter. Its background set contains a bit for every position$^8$ of the counter: $S_{01} = \{1_i | 0 \le i < t\}$. For example, the binary number 1101 is represented by the state $\{1_3, 1_2, 1_0\}$.

The set $A_{01}$ contains two types of reactions:

$$ A_{01} = \{\text{keep}_{ij} : (\{1_i\}, \{1_j\}, \{1_i\}) \mid 0 \le j < i < t\} \cup \{\text{set}_i : (\{1_j | 0 \le j < i\}, \{1_i\}, \{1_i\}) \mid 0 \le i < t\}. $$

The reactions $keep_{ij}$ keep the bit $1_i$ set if at least one of the less significant bits is unset. A reaction $set_i$ sets the bit $1_i$ if it was not already set, and if all less significant bits are set. To see that these reactions indeed implement the binary increment, consider the following possibilities for bit $i$:

* Bit $i$ is 1:

- Some less significant bits $j$ are 0: The least significant $j$ will be flipped to 1 to accommodate addition or carry—one of the reactions $keep_{ij}$ is enabled.

- All of the less significant bits $j$ are 1: Bit $i$ should be flipped to 0 because of the carry. No reactions are enabled (note that $set_i$ requires bit $i$ to be 0 to be enabled).

* Bit $i$ is 0:

- Some less significant bits $j$ are 0: The least significant bit $j$ will be flipped to 1 to accommodate addition or carry, so bit $i$ stays 0—no reactions are enabled.

- All less significant bits $j$ are 1: Bit $i$ must flip to 1 because of the carry—reaction $set_i$ is enabled.

Finally note that the binary counter implemented by $A_{01}$ is cyclic: $res_{A_{01}}(S_{01}) = \emptyset$, and $res_{A_{01}}(\emptyset) = \{1_0\}$ because $\text{set}_0 : (\emptyset, \{1_0\}, \{1_0\})$ is enabled in $\emptyset$.

The reaction system $A_{01}$ is therefore a busy beaver champion with respect to the frame $\mathcal{F}_{per}$: it achieves the longest possible period for a fixed sized of the background set.

**Proposition 1** Given the size function $size: \mathcal{A} \to \mathbb{N}$, $size(\mathcal{A}) = |S_\mathcal{A}|$, a fixed size $n \in \mathbb{N}$, and the busy beaver frame $\mathcal{F} = \mathcal{F}_{per}(size, n)$ (Sect. 4.3.2), the longest period of a busy beaver champion is $\mu_\mathcal{F} = 2^n$.

Because the observed property in the busy beaver frame for longest runs $\mathcal{F}_{lr}$ is the appearance of the first empty set, the reaction system $A_{01}$ also features the longest possible run in this sense. Indeed, start with the state $\{1_0\}$ and let the counter run to its maximal value $S$, which will be followed by the state $\emptyset$ since $res_{A_{01}}(S_{01}) = \emptyset$. Thus $A_{01}$ will cycle through all possible subsets of $S_{01}$ before finally reaching $\emptyset$ after $2^n - 1$ steps.

**Proposition 2** Given the size function $size: \mathcal{A} \to \mathbb{N}$, $size(\mathcal{A}) = |S_\mathcal{A}|$, a fixed size $n \in \mathbb{N}$, and the busy beaver frame $\mathcal{F} = \mathcal{F}_{lr}(size, n)$ (Sect. 4.3.1), the longest run of a busy beaver champion is $\mu_\mathcal{F} = 2^n - 1$.

On the other hand, the reaction system $A_{01}$ is not a busy beaver champion in the frame $\mathcal{F}_{per}$ (Sect. 4.3.3). Indeed, the cycle implemented in $A_{01}$ traverses all states in $2^{|S_{01}|}$, so the preperiod is of length 0 whatever the initial context $C_0$. On the other hand, as the total number of states of a reaction system $\mathcal{A}$ is $2^{|S_\mathcal{A}|}$, the longest preperiod of $2^{|S_\mathcal{A}|} - 1$ would be obtained if $\mathcal{A}$ reached a fixed point $W$ after traversing all other states in $2^{|S_\mathcal{A}|} \setminus \{W\}$. It is possible to

<footnote>$^8$ The indexes of positions are 0-based in our counter to match the powers of 2, i.e., the least significant bit is $1_0$ and the most significant bit is $1_{t-1}$.</footnote>
obtain such a reaction system by modifying $A_{01}$ from Example 5.

**Example 6** Consider $A'_{01} = (S_{01}, A'_{01})$, with the set of reactions obtained as follows:

$$A'_{01} = A_{01} \setminus \{set_0\} \cup \{set_0^x : (\{x\}, \{1_0\}, \{1_0\}) \mid x \in S \setminus \{1_0\}\}.$$

In $A'_{01}$, $set_0$ is replaced by reactions $set_0^x$ which ensure the same behavior as $set_0$, except for the empty set: $\text{res}_{A'_{01}}(W) = \text{res}_{A_{01}}(W)$ for all non-empty $W \subseteq S_{01}$, and $\text{res}_{A'_{01}}(\emptyset) = \emptyset$, since no reactions in $A'_{01}$ are enabled in $\emptyset$. Intuitively, $A'_{01}$ implements a binary counter except for the empty state in which $A'_{01}$ does not introduce the least significant bit $1_0$ (as opposed to $A_{01}$).

The reaction system $A'_{01}$ is a busy beaver champion with respect to the frame $\mathcal{F}_{pper}$: starting from the state $\{1_0\}$ it first counts through $2^{|S_{01}|} - 1$ subsets of $S_{01}$, and stops evolving after reaching $\emptyset$.

**Proposition 3** Given the size function $\text{size}: \mathcal{A} \to \mathbb{N}$, $\text{size}(\mathcal{A}) = |S_{\mathcal{A}}|$, a fixed size $n \in \mathbb{N}$, and the busy beaver frame $\mathcal{F} = \mathcal{F}_{pper}(\text{size}, n)$ (Sect. 4.3.3), the preperiod of a busy beaver champion is $\mu_{\mathcal{F}} = 2^n - 1$.

As is apparent from the definitions of the busy beaver frame and the generalized busy beaver game, the maximal values $\mu_{\mathcal{F}}$ may generally be achieved by multiple different reaction systems. For example, cycling through all possible states can be done by fixing any ordering on the subsets of the background set and having reactions precisely drive the system from one of these subsets to the next one.

**Example 7** Consider a background set $S$, fix an ordering on the set of its subsets $w = (W_i)_{1 \le i \le 2^{|S|}}$, $W_i \subseteq S$, and construct the following set of reactions:

$$A_{enum} = \{(W_i, S \setminus W_i, W_{i+1}) \mid 1 \le i < 2^{|S|} \} \cup \{(W_{2^{|S|}}, S \setminus W_{2^{|S|}}, W_1)\}.$$

Finally, define $A_{enum} = (S, A_{enum})^9$. Note that $\text{res}_{A_{enum}}(W_i) = W_{i+1}$ for any subset $W_i$ except the last one $W_{2^{|S|}}$. Indeed, the only reaction enabled in such a $W_i$ is $(W_i, S \setminus W_i, W_{i+1})$, and all other reactions are disabled because of their inhibitor sets. On the other hand, the only reaction enabled in the last set $W_{2^{|S|}}$ is $(W_{2^{|S|}}, S \setminus W_{2^{|S|}}, W_1)$, meaning that $\text{res}_{A_{enum}}(W_{2^{|S|}}) = W_1$. Therefore, $A_{enum}$ cycles through the subsets in $w$, in order.

Consider again the background set $S_{01}$ from Example 5 and order its subsets by the corresponding numerical values. More concretely, define $\text{val}: 2^{S_{01}} \to \mathbb{N}$, $\text{val}(W) = \sum_{1 \le i \le W} 2^i$, and define the ordering $(W_i)_{1 \le i \le 2^{|S|}}$

such that $i = 1 + \text{val}(W_i)$. Then the behavior of the corresponding instance of $A_{enum}$ from Example 7 will be exactly the same as that of $A_{01}$ from Example 5. Furthermore, $A_{enum}$ can be modified by removing the reaction $(W_{2^{|S|}}, S \setminus W_{2^{|S|}}, W_1)$, and the behavior of the new reaction system $A'_{enum}$ can similarly be brought to be the same as that of $A'_{01}$ from Example 6. Therefore, $A_{enum}$ is also a busy beaver champion in the frames $\mathcal{F}_{pper}$ and $\mathcal{F}_{lr}$, while $A'_{enum}$ is a busy beaver champion in the frame $\mathcal{F}_{pper}$.

## 5.2 Empty reactants and inhibitors not allowed

Several constructions shown above rely on empty reactant or inhibitor sets, e.g., the reaction $set_0 : (\emptyset, \{1_0\}, \{1_0\})$ from Example 5. On the other hand, the reaction system $A'_{01}$ from Example 6 features no reactions with empty reactant or inhibitor sets. Proposition 3 can therefore be directly transposed to $A_{-\emptyset}$.

**Proposition 4** Consider the class of reaction systems $A_{-\emptyset}$ with non-empty reactant and inhibitor sets. Given the size function $\text{size}: A_{-\emptyset} \to \mathbb{N}$, $\text{size}(\mathcal{A}) = |S_{\mathcal{A}}|$, a fixed size $n \in \mathbb{N}$, and the busy beaver frame $\mathcal{F} = \mathcal{F}_{pper}^{A_{-\emptyset}}(\text{size}, n)$, the longest preperiod of a busy beaver champion is $\mu_{\mathcal{F}} = 2^n - 1$.

Furthermore, since $\emptyset$ is the only fixed point of $A'_{enum}$, this reaction system also wins the busy beaver game focused on longest runs, allowing once again to directly transpose the statement of Proposition 2 to $A_{-\emptyset}$.

**Proposition 5** Consider the class of reaction systems $A_{-\emptyset}$ with non-empty reactant and inhibitor sets. Given the size function $\text{size}: A_{-\emptyset} \to \mathbb{N}$, $\text{size}(\mathcal{A}) = |S_{\mathcal{A}}|$, a fixed size $n \in \mathbb{N}$, and the busy beaver frame $\mathcal{F} = \mathcal{F}_{lr}^{A_{-\emptyset}}(\text{size}, n)$, the longest run of a busy beaver champion is $\mu_{\mathcal{F}} = 2^n - 1$.

The case of the busy beaver game focused on longest periods is less immediate. Notice at first that the restriction to not have empty reactant sets implies that $\emptyset$ is always a fixed point. More formally, for any $A \in A_{-\emptyset}$, $\text{res}_A(\emptyset) = \emptyset$. Furthermore, for such reaction systems $\text{res}_A(S)$ must be empty, because all inhibitor sets are non-empty and all possible inhibitors are present in $S$. Therefore, the longest period we can expect in $A_{-\emptyset}$ is $2^{|S|} - 2$, two less than the period length achieved by $A_{01} \notin A_{-\emptyset}$ from Example 5. It is rather straightforward to patch the reaction system $A_{enum}$ from Example 7 to achieve a period of this length.

**Example 8** Consider a background set $S$ and fix an ordering on all of its subsets except $\emptyset$ and $S$: $w = (W_i)_{1 \le i \le 2^{|S|-2}}$, $W_i \in 2^S \setminus \{\emptyset, S\}$. Construct the following set of reactions for $w$:

<footnote n="9">⁹ Both $A_{enum}$ and $A_{enum}$ are implicitly parameterized by $S$, but we avoid writing $A_{enum}(S)$ and $A_{enum}(S)$ to simplify notations.</footnote>
$$A'_{enum} = \{(W_i, S \setminus W_i, W_{i+1}) \mid 1 \le i < 2^{|S|} - 2\} \cup \{(W_{2^{|S|}-2}, S \setminus W_{2^{|S|}-2}, W_1)\}$$

Define $\mathcal{A}'_{enum} = (S, A_{enum})$. $A'_{enum}$ is constructed in exactly the same way as $A_{enum}$ from Example 7, except that its reactions always have non-empty reactant and inhibitor sets because $W_i \notin \{\emptyset, S\}$. The main period of $\mathcal{A}'_{enum}$ cycles through the subsets in the sequence $w$ in order, because $\mathrm{res}_{\mathcal{A}'_{enum}}(W_i) = W_{i+1}$ for all $1 \le i < 2^{|S|} - 2$, and $\mathrm{res}_{\mathcal{A}'_{enum}}(W_{2^{|S|}-2}) = W_1$. The behavior of $\mathcal{A}'_{enum}$ on $\emptyset$ and $S$ follows the remarks in the paragraphs before this example: $\mathrm{res}_{\mathcal{A}'_{enum}}(S) = \mathrm{res}_{\mathcal{A}'_{enum}}(\emptyset) = \emptyset$.

Modifying $A_{01}$ from Example 5 or $\mathcal{A}'_{01}$ from Example 6 to cycle through all the subsets of $S_{01}$ except $\emptyset$ and $S_{01}$ is nontrivial. As discussed at the beginning of this section, $\mathcal{A}'_{01}$ is already in $A_{-\emptyset}$, but its longest period is of length 1 and consists of the empty set $\emptyset$. To make a reaction system that would behave like $\mathcal{A}'_{01}$, but would additionally avoid the state $S_{01}$, we focus on the following transition ensured by the reactions $keep_{ij}$ and $set_0^x$:

$$S_{01} \setminus \{1_0\} = \{1_{t-1}, 1_{t-2}, \dots, 1_1\} \rightarrow \{1_{t-1}, 1_{t-2}, \dots, 1_1, 1_0\} = S_{01}$$

The desired behavior would be to avoid reaching $S_{01}$ and subsequently $\emptyset$, but instead transitioning from $S_{01} \setminus \{1_0\}$ directly to $\{1_0\}$ and thus restarting the counter. The following construction shows how this can be achieved by modifying the reactions $keep_{ij}$.

**Example 9** Consider the reaction system $\mathcal{A}''_{01} = (S_{01}, A''_{01})$ with the following set of reactions:

$$\begin{align*}
\mathcal{A}''_{01} &= \{\mathrm{keep}_{ij} : (\{1\}, \{1, 1_k\}, \{1_i\}) \mid 0 \le j < i < t, k \in \{1, \dots, t-1\} \setminus \{i, j\}\} \\
\cup \quad &\{\mathrm{keep}'_{ij} : (\{1, 1_0\}, \{1\}, \{1_i\}) \mid 0 \le j < i < t\} \\
\cup \quad &\{\mathrm{set}_i : (\{1_j\} \mid 0 \le j < i\}, \{1_i\}, \{1_j\}) \mid 0 < i < t\} \\
\cup \quad &\{\mathrm{set}_0^x : (\{x\}, \{1_0\}, \{1_0\}) \mid x \in S\},
\end{align*}$$

where $t$ is the number of bits in the binary counter, as in Example 5. In other words, $\mathcal{A}''_{01}$ is obtained from the set $\mathcal{A}'_{01}$ by removing all the reactions $keep_{ij}$ and adding the reactions $keep_{ijk}$ and $keep'_{ij}$ instead.

Reactions $keep_{ijk}$ reproduce the behavior of $keep_{ij}$ for all subsets of $S_{01}$ which are missing at least one other bit $1_k$. Denote $K_{ij} = \{\mathrm{keep}_{ijk} \mid k \in \{1, \dots, t-1\} \setminus \{i, j\}\}$. Then $\mathrm{res}_{\mathrm{keep}_{ij}}(W) = \mathrm{res}_{K_{ij}}(W)$ for all $W \subseteq S_{01}$ such that $|S_{01} \setminus W| \ge 2$. On the other hand, none of the reactions $keep_{ijk}$ is enabled in states $W'$ of the form $S_{01} \setminus \{1_j\}$ for some $0 < j < t$. The role of reactions $keep'_{ij}$ is to keep the bits $1_i, i > j$, in such states. Indeed, all such states contain $1_0$ by construction, so $\mathrm{res}_{\mathrm{keep}_{ij}}(W') = \mathrm{res}_{\mathrm{keep}'_{ij}}(W')$, for all $W' \in \{S_{01} \setminus \{1_j\} \mid 0 < j < t\}$.

Note that the states in which the reactions from $K_{ij} \cup \{\mathrm{keep}'_{ij}\}$ are enabled form a strict subset of the states in

which $keep_{ij}$ is enabled, meaning that none of these new reactions will keep a bit $1_i$ where $keep_{ij}$ would not.

Finally, the role of reactions $set_i$ and $set_0^x$ are as in Examples 5 and 6: they set the bit $1_i$ whenever all less significant bits $1_j$ are already set.

From the observations above we conclude that the behavior of $\mathcal{A}''_{01}$ is the same as that of $\mathcal{A}'_{01}$, except for the state $S_{01} \setminus \{1_0\}$. The only reactions enabled in this state are $set_0^x$ for $x \in S_{01} \setminus \{1_0\}$, meaning that $\mathrm{res}_{\mathcal{A}''_{01}}(S_{01} \setminus \{1_0\}) = \{1_0\}$. In other words, the reaction system $\mathcal{A}''_{01}$ is a binary counter which skips the states $\emptyset$ ($\mathrm{val}(\emptyset) = 0$) and $S_{01}$ ($\mathrm{val}(S_{01}) = 2^t - 1$).

Based on the constructions in Examples 8 and 9, we conclude that the maximal length of the period is indeed achieved by some reaction systems in $A_{-\emptyset}$.

**Proposition 6** Consider the class of reaction systems $A_{-\emptyset}$ with non-empty reactant and inhibitor sets. Given the size function size: $A_{-\emptyset} \rightarrow \mathbb{N}$, size($A$) = $|S_A|$, a fixed size $n \in \mathbb{N}$, and the busy beaver frame $\mathcal{F} = \mathcal{F}_{\mathrm{per}}(\mathrm{size}, n)$ (Sect. 4.3.2), the longest period of a busy beaver champion is $\mu_{\mathcal{F}} = 2^n - 2$.

# 6 The busy beaver game for size($A$) = $|A|$

The constructions for enumerating states in the previous section all revolve around one of the following two ideas: either use reactions enabled in one state and one state only (e.g., $A_{enum}$ from Example 7), or use a variation of the binary counter (e.g., $A_{01}$ from Example 5). While both kinds of constructions can be used to win the busy beaver game with the size function accounting for the size of the background set, the number of employed reactions is quite different. $A_{01}$ contains one reaction $set_i$ for every bit in the background set $S_{01}$, plus one reaction for every pair $1_i$ and $1_j, 0 \le i < j < t$, totalling to: $|A_{01}| = t + t(t+1)/2 = t(t+3)/2 = O(t^2)$ reactions. $A_{enum}$ on the other hand would include a reaction for every subset of $S_{01}$, meaning that $|A_{enum}| = 2^t$.

In this section we explore the generalized busy beaver game for the size function measuring the cardinality of the set of reactions, i.e., for $A = (S_A, A)$, size($A$) = $|A|$. In particular, we establish several bounds on the maximal values $\mu_{\mathcal{F}}$ that can be achieved for different frames $\mathcal{F}$. We start by highlighting a natural concept for reaction systems.

## 6.1 Effective state space

**Definition 5** For a reaction system $A = (S_A, A)$, the effective state space is the set of all states reachable by $A$: $\mathrm{esp}(A) = \{\mathrm{res}_A(W) \mid W \subseteq S_A\}$.
The fact that applying a reaction $a \in A$ to a set $W$ always results in just the set of its products $P_a = \text{res}_a(W)$ means that the form of the effective state space is constrained by unions of the product sets.

**Lemma 7** For a reaction system $\mathcal{A} = (S_A, A)$ the following holds:

$$ \text{esp}(\mathcal{A}) \subseteq \{ \bigcup_{a \in A'} P_a \mid A' \subseteq A \}. $$

**Proof** The effective state space is the result of all possible applications of reactions in $\mathcal{A}$, and the result of applying a set of enabled reactions $A' \subseteq A$ to a state $W$ is $\bigcup_{a \in A'} P_a$ by definition (Sect. 2.2). On the other hand, not all subsets of $\mathcal{A}$ can be enabled in the same state $W$, meaning that in general the inclusion from the statement of the lemma is not necessarily strict. $\square$

Lemma 7 directly gives a bound on the size of the effective state space in terms of the number of reactions in $\mathcal{A}$.

**Lemma 8** For any reaction system $\mathcal{A} = (S_A, A)$, it is true that $|\text{esp}(\mathcal{A})| \le 2^{|A|}$.

**Proof** One of the situations in which the set $\{\bigcup_{a \in A'} P_a \mid A' \subseteq A\}$ in Lemma 7 contains the most unions is when all product sets $P_a$ are pairwise disjoint. In this case, the unions $\bigcup_{a \in A'} P_a$ are different for different subsets $A' \subseteq A$. Since there are $2^{|A|}$ subsets of $A$, there are $2^{|A|}$ such unions, which implies the statement of the lemma. $\square$

Lemma 8 shows that the background set is not the only limiting factor of the size of the effective state space. Indeed, when the number of distinct product sets $P_a$ is comparable to the number of individual species in $S_A$, the upper bound $2^{|A|}$ is effectively the same as $2^{|S_A|}$—the number of all possible subsets of $S_A$. When on the other hand the number of product sets (or reactions) is significantly smaller than the number of species, the bound $2^{|A|}$ becomes central in determining the size of $\text{esp}(\mathcal{A})$. In particular, the upper bound from Lemma 8 has direct consequences for the length of runs, periods, and preperiods as a function of the $|A| = \text{size}(\mathcal{A})$, as the following section shows.

**Remark 6** A subtle but important difference between the two size measures considered so far—$\text{size}(\mathcal{A}) = |S_A|$ and $\text{size}(\mathcal{A}) = |A|$—concerns the finiteness of $\mathcal{R}S(n)$. Fixing the size of the background set $S_A$ ($\text{size}(\mathcal{A}) = |S_A|$) bounds the number of effectively different reaction systems. Indeed, since the individual species in $S_A$ do not have structure, the only relevant parameter of the background set is its size. For a fixed background set $S_A$ there are $2^{|S_A|}$.

$2^{|S_A|} \cdot 2^{|A|} = 2^{3|S_A|}$ possible reactions, and thus $2^{3|S_A|}$ distinct collections of reactions and distinct reaction systems. Fixing the number of reactions on the other hand ($\text{size}(\mathcal{A}) = |A|$) does not bound the number of distinct reaction systems, because it does not bound the size of the background set. Thus, there are infinitely many distinct reaction systems with the same number of reactions.

## 6.2 Bounds on busy beaver maxima

Recall that we are only considering seeded interactive processes in our framework for the busy beaver game. In such interactive processes, the initial context $C_0$ is not necessarily in the effective state space, but all subsequent states are in $\text{esp}(\mathcal{A})$ by construction. In particular, all states of any period of $\mathcal{A}$ must be in $\text{esp}(\mathcal{A})$, yielding the following bound.

**Proposition 9** Given the size function size: $\mathcal{A} \to \mathbb{N}$, size($\mathcal{A}$) = $|A|$, a fixed size $n \in \mathbb{N}$, and the busy beaver frame $\mathcal{F} = \mathcal{F}_{per}(\text{size}, n)$ the longest period of a busy beaver champion is at most $\mu_{\mathcal{F}} \le 2^n$.

Longest preperiods are similarly restricted. Indeed, fixed points have longest preperiods, and a fixed point is necessarily in $\text{esp}(\mathcal{A})$. Therefore, the longest preperiod one could hope for consists of an initial context $C_0 \notin \text{esp}(\mathcal{A})$, followed by $2^{|\text{esp}(\mathcal{A})|} - 1 \le 2^{|A|} - 1$ states from the effective state space, and is therefore of length at most $2^{|A|} - 1 + 1 = 2^{|A|}$.

**Proposition 10** Given the size function size: $\mathcal{A} \to \mathbb{N}$, size($\mathcal{A}$) = $|A|$, a fixed size $n \in \mathbb{N}$, and the busy beaver frame $\mathcal{F} = \mathcal{F}_{pper}(\text{size}, n)$ the longest preperiod of a busy beaver champion is at most $\mu_{\mathcal{F}} \le 2^n$.

Similar reasoning applies to the longest run. The empty state $\emptyset$ must be in $\text{esp}(\mathcal{A})$ since $\mathcal{A}$ must reach it. Therefore, the longest run must start in an initial context $C_0 \notin \text{esp}(\mathcal{A})$ and then traverse as many states in $\text{esp}(\mathcal{A}) \setminus \{\emptyset\}$ as possible, thus at most $2^{|A|} - 1$ states.

**Proposition 11** Given the size function size: $\mathcal{A} \to \mathbb{N}$, size($\mathcal{A}$) = $|A|$, a fixed size $n \in \mathbb{N}$, and the busy beaver frame $\mathcal{F} = \mathcal{F}_{lr}(\text{size}, n)$ the longest run of a busy beaver champion is at most $\mu_{\mathcal{F}} \le 2^n$.

In the discussions above no restrictions on the shape of reactions are considered. Nevertheless, the arguments of Lemmas 7 and 8 hold unchanged even if empty reactant or inhibitor sets are not allowed, maintaining the same upper bounds for $\mathcal{A}_{-\emptyset}$.

**Proposition 12** Consider the class of reaction systems $\mathcal{A}_{-\emptyset}$ with non-empty reactant and inhibitor sets. Given the size
function **size**: $A_{-\emptyset} \to \mathbb{N}$, $\text{size}(A) = |A|$, a fixed size $n \in \mathbb{N}$, and a busy beaver frame $F_X = F_{X-\emptyset}^{A}$ ($\text{size}, n$) the busy beaver maxima are bounded by $\mu_{F_X} \le 2^n$, for any $X \in \{\text{per}, \text{pper}, \text{lr}\}$.

Another observation we draw from the bound in Lemma 8 as well as the subsequent propositions in this section concerns the limit to how far one can reduce the number of reactions while maintaining the same size of the behavior. More concretely, to achieve periods, preperiods, or runs of some target length *l*, a reaction system has to have $\Omega(\log_2 l)$ reactions.<fnref n="10" /> This leads to the following conjecture.

**Conjecture 13** *Busy beaver champions for the frames* $\mathcal{F}_X(\mathbf{size}, n)$, $X \in \{\text{per}, \text{pper}, \text{lr}\}$, *in A and A$_{-\emptyset}$, are based on a variant of the binary counter similar to Example 5.*

Among the variations of the binary counters shown in Sect. 5, $\mathcal{A}_{01}$ from Example 5 uses the fewest reactions: $|A_{01}| = t(t+3)/2$, where $t = |S_{01}|$ is the number of bits of the counter. Indeed, in $\mathcal{A}'_{01}$ from Example 6 a single reaction $set_0$ is replaced by $t-1$ reactions $set_0^x$, while in $\mathcal{A}''_{01}$, the $t(t+1)/2$ reactions $keep_{ij}$ are additionally replaced by a reaction $keep'_{ij}$ plus $O(t^3)$ reactions $keep_{ijk}$. It is yet unclear whether the number of reactions in a busy beaver champion can be further reduced to achieve the maximal values using fewer reactions.

## 7 Conclusions

In this paper we focused on transposing the busy beaver game initially conceived for Turing machines to reaction systems. This translation is non-trivial because reaction systems are quite different from Turing machines: as a model of computing, they belong to the family of set rewriting and therefore feature a finite state space. Furthermore, the dynamics of reaction systems is given by interactive processes closely driven by context sequences. To address the latter specificity, we proposed seeded interactive processes (Definition 4) mimicking the notion of a run starting in a given state and receiving no further input later on.

The finiteness of the state space makes the problem of identifying the longest run much less complex than in the case of Turing machines, and solvable by a classic construction of the binary counter (Example 5). This inspired us to generalize the kinds of features that can be optimized for in the busy beaver challenge, and lead to introducing a

generalized framework for the game (Sect. 4). This framework is based on the concept of the busy beaver frame, which provides a setup for observing some general non-local features, and measuring the time distance—i.e., the number of states in the interactive process—between them. We further provided instantiations of the generalized framework to some well-understood features, like periods, preperiods, runs to a fixed point, etc.

Even if the simplest busy beaver challenge focusing on the longest period with the size measuring the size of the background set is easily won by the binary counter from Example 5, identifying busy beaver champions for the other frames is less trivial (Sect. 5.1). If additionally empty reactant and inhibitor sets are not allowed, the binary counter still wins, but a series of modifications are required (Example 9).

Switching the **size** function to measure the cardinality of the set of reactions makes finding busy beaver champions harder. We highlight the notion of the effective state space (Sect. 6.1) which allows us to establish a series of bounds on the size of behavior that can be achieved by a reaction system with a given cardinality of the set of reactions. As we point out in Conjecture 13, we believe that busy beaver champions with respect to this size measure will still be variations of the binary counter.

## 8 The meaning of life

Allen H. Brady titles his paper “The Busy Beaver Game and the Meaning of Life” (Brady 1988), in reference to the title of Conway’s famous Game of Life: a 2-dimensional cellular automaton whose patterns like gliders, spaceships, blinkers, etc. are a mainstay in the popular culture. One of our goals behind considering the busy beaver challenge is to give it a meaning in thinking about *actual* biological life. This goal is directly motivated by reaction systems claiming inspiration from biochemical reactions (Ehrenfeucht and Rozenberg 2007) and by the original idea of a busy beaver champion running—or *surviving*—the longest.

In this context, the finiteness of the state space becomes a feature, not a bug: real-world biological systems run in bounded space and with limited resources. The implications of potential infinity in more powerful models of computing—unbounded tape in Turing machines, unbounded numbers in register machines, etc.—are subtle, but significant. As complexity theory conveniently highlights with the polynomial hierarchy<fnref n="11" /> and complexity classes beyond PSPACE, the Turing machine can in principle solve very complex problems, but may require prohibitive time and infeasible amounts of resources.

<footnote n="10">¹⁰ Following Knuth’s work (Knuth 1976; Wikipedia contributors 2025a), we use the “big omicron” notation to mean the opposite of the big O notation, i.e., $f(x) = \Omega(g(x)) \Leftrightarrow g(x) = O(f(x))$. Intuitively, this means that $f$ is bounded by $g$ from below.</footnote>

<footnote n="11">¹¹ The hierarchy of complexity classes starting with the class P and contained in PSPACE (Wikipedia contributors 2025b).</footnote>
Reaction systems on the other hand always run within the bounds imposed by the background set of species. The definition of the dynamics via interactive processes processes and the absence of the classical notion of halting in the sense of automata theory is also relevant, as it shifts the focus from obtaining a result from an input to observing the entire evolution, which may be seen as a counterpart of following the life of a simple organism.

Taking reaction systems as a representation of a living organism has clear limitations, notably from the structural complexity point of view. Indeed, most organisms—even the simplest ones—have quite complex spatial organisation. Viruses for example feature a protein shell (capsid) containing a small amount of genetic material, and having some mechanical properties which ensure that the virus can interact with the appropriate receptors on the cell membrane. The abstraction of set rewriting cannot capture even this relatively simple set of behaviors, which can be better characterized using other modelling tools involving continuous space (Lidmar et al. 2003) as a random example).

We therefore follow the line of thought from the previous works (Alhazov et al. 2024, 2024; Segretain et al. 2021; Glade 2022) and instead of using reaction systems as *models* of biological systems, i.e., instead of faithfully representing some target features (as done in e.g., Azimi et al. (2015, 2014)), we consider reaction systems as a very high level image, only paralleling actual organisms in the fact that they are resource-consuming dynamical systems. In particular, the generalized framework for the busy beaver game we proposed in Sect. 4.2 can be used to formulate different competition criteria, thought of as similar coarse-grained representation of natural selection. We expect that further exploration of different variants of the busy beaver challenge may yield interesting intuitions with regard to the variation of complexity of the biological systems during evolution, in the spirit of Segretain et al. (2021) which focuses on Boolean networks—a dynamical system closely related to reaction systems.

# 9 Future work

We classify the directions for future work on busy beaver games for reaction systems in three main categories, two dealing with the technical aspects of the challenge, and one focusing on interpretations in theoretical biology.

**Further bounds and champions** In this paper, we did not give a concrete busy beaver champion for *size* function measuring the size of the set of reactions. We only gave a series of bounds in Sect. 6, and it would be interesting to make them more precise, hopefully to the point where concrete busy beaver champions can be provided. Furthermore, other bounds may be established for other *size* functions measuring different parameters of the reaction system. In particular, the entire body of literature on insertion-deletion

systems (e.g., Alhazov et al. (2024)) seems to hint that measuring the sizes of reaction components separately may be a tool for fine exploration of optimization strategies inherent in the busy beaver game. Indeed, while the reactions *keep*<sub>*ij*</sub> in Example 5 have singleton components, the reactions *set*<sub>*i*</sub> may have very large reactant sets, with *set*<sub>*j*−1</sub> having the entire *S*<sub>01</sub> \ {1<sub>*j*</sub>} as reactants. Limiting the size of the reactant set could require many more reactions to implement a sort of a binary counter, or even impose a departure from the counter approach altogether. Finally, the constructions in this paper bear some similarity to other works studying the computational complexity aspects of reaction systems (e.g., Dennunzio et al. (2019)), which opens up a whole family of questions concerning the computational complexity of identifying busy beaver champions.

**Programmatic enumeration** Recent years have shown that exhaustive enumeration of candidates as done in The Busy Beaver Challenge (2024) is a powerful instrument in finding and proving results about the busy beaver game. This approach seems even more feasible for reaction systems, since they are a much simpler model of computing than Turing machines. Furthermore, deriving optimization strategies and bounds from such automatic enumeration should be considerably easier as well, since the semantics of application of reactions is easier to interpret.

**Origins of life** As pointed out in Sect. 8, reaction systems present several features making them an interesting candidate for thinking about evolution and the origins of life, together with other models of natural computing like membrane (P) systems, Boolean networks, cellular automata, etc. We hope that the line of work started in this paper sparks new research on using reaction systems as support for abstract thought about many hard problems in theoretical biology.

**Acknowledgements** Artiom Alhazov acknowledges Project 011301 "Information systems based on artificial intelligence" by Moldova State University. All authors acknowledge the anonymous reviewers for their helpful comments.

**Author Contributions** All authors contributed equally to this work.

**Funding** Open access funding provided by Université d'Évry Vald'Essonne.

**Data Availability** No datasets were generated or analysed during the current study.

# Declarations

**Conflict of interest** The authors declare no conflict of interest.

**Open Access** This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the
source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

## References

Alhazov A, Freund R, Ivanov S (2024) On the spectrum between reaction systems and string rewriting. Nat Comput 23(2):159–175. https://doi.org/10.1007/S11047-024-09986-1

Alhazov A, Freund R, Ivanov S, Orellana-Martín D, Ramírez-de-Arellano A, Rodríguez-Gallego J (2024) P systems with reactive membranes. J Membr Comput 6(2):82–93. https://doi.org/10.1007/S41965-024-00144-1

Alhazov A, Ivanov S, Orellana-Martín D (2024) Queens of the hill. J Membr Comput 6(3):193–201. https://doi.org/10.1007/S41965-024-00152-1

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–371

Alhazov A, Aman B, Freund R, Ivanov S (2016) Simulating R systems by P systems. 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–66. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-319-54072-6_4

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–113. https://doi.org/10.1016/J.TCS.2015.11.040

Azimi S, Gratie C, Ivanov S, Petre I (2015) Dependency graphs and mass conservation in reaction systems. Theor Comput Sci 598:23–39. https://doi.org/10.1016/J.TCS.2015.02.014

Azimi S, Iancu B, Petre I (2014) Reaction system models for the heat shock response. Fundam Informaticae 131(3–4):299–312. https://doi.org/10.3233/FI-2014-1016

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–277

Brijder R, Ehrenfeucht A, Main MG, Rozenberg G (2011) A tour of reaction systems. Int J Found Comput Sci 22(7):1499–1517. https://doi.org/10.1142/S0129054111008842

Cavaliere M, Freund R, Oswald M, Sburlan D (2007) Multiset random context grammars, checkers, and transducers. Theor Comput Sci 372(2–3):136–151. https://doi.org/10.1016/J.TCS.2006.11.022

Dennunzio A, Formenti E, Manzoni L (2015) Reaction systems and extremal combinatorics properties. Theor Comput Sci 598:138–149. https://doi.org/10.1016/J.TCS.2015.06.001

Dennunzio A, Formenti E, Manzoni L, Porreca AE (2019) Complexity of the dynamics of reaction systems. Inf Comput 267:96–109. https://doi.org/10.1016/j.ic.2019.03.006

Dennunzio A, Formenti E, Manzoni L, Porreca AE (2015) Ancestors, descendants, and gardens of Eden in reaction systems. Theor Comput Sci 608:16–26 https://doi.org/10.1016/j.tcs.2015.05.046. From Computer Science to Biology and Back

Ehrenfeucht A, Rozenberg G (2007) Reaction systems. Fundam Informaticae 75(1–4):263–280

elementary set theory - Collection of all finite sets - Mathematics stack exchange. https://math stackexchange.com/a/896291. [Online; accessed 2025-03-10]

Freund R, Ivanov S, Staiger L (2016) Going beyond turing with P automata: regular observer o-languages and partial adult halting. Int J Unconv Comput 12(1):51–69

Glade N (2022) Le Vivant Rare, Faible et Amorphe - Évolution Depuis les Origines Jusqu'à la Vie Telle Qu'elle Nous Apparaît. (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

Ivanov S, Petre I (2020) Controllability of reaction systems. J Membr Comput 2(4):290–302. https://doi.org/10.1007/S41965-020-00055-X

Knuth DE (1976) Big omicron and big omega and big theta. SIGACT News 8(2):18–24. https://doi.org/10.1145/1008328.1008329

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

Męski A, Koutny M, Penczek W (2017) Verification of linear-time temporal properties for reaction systems with discrete concentrations. Fund Inform 154:289–306. https://doi.org/10.3233/FI-2017-1567

Męski A, Penczek W, Rozenberg G (2015) Model checking temporal properties of reaction systems. Inf Sci 313:22–42. https://doi.org/10.1016/j.ins.2015.03.048

Radó T (1962) On non-computable functions. Bell Syst Tech J 41(3):877–884

Rozenberg G, Salomaa A (eds) (1997) Handbook of formal languages, vol 1–3. Springer, Berlin Heidelberg. https://doi.org/10.1007/978-3-642-59136-5

Salomaa A (2012) Functions and sequences generated by reaction systems. Theor Comput Sci 466:87–96. https://doi.org/10.1016/J.TCS.2012.07.022

Salomaa A (2013) Functional constructions between reaction systems and propositional logic. Int J Found Comput Sci 24(1):147–160. https://doi.org/10.1142/S0129054113500044

Salomaa A (2015) Two-step simulations of reaction systems by minimal ones. Acta Cybern 22(2):247–257. https://doi.org/10.14232/actacyb.22.2.2015.2

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–446. https://doi.org/10.1007/978-3-319-13350-8_32

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–6. IEEE, New York. https://doi.org/10.1109/BIBE52308.2021.9635403

Stérin T, Woods D (2024) Hardness of busy beaver value BB(15). In: Kovács, 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–137. Springer, Cham. https://doi.org/10.1007/978-3-031-72621-7_9

The reaction systems webpage. https://www.reactionsystems.org/. [Online; accessed 2025-02-13]

The busy beaver challenge. https://bbchallenge.org/. [Online; accessed 2025-02-13] (2024)

Wikipedia contributors: big O notation — Wikipedia, The Free Encyclopedia. https://en.wikipedia.org/w/index.php?title=Big_
O_notation&oldid=1282096187. [Online; accessed 24-March-2025] (2025)

Wikipedia contributors: Polynomial hierarchy — Wikipedia, The Free Encyclopedia. https://en.wikipedia.org/w/index.php?title=Polynomial_hierarchy&oldid=1279707173. [Online; accessed 26-March-2025] (2025)

Publisher's Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.