4
$\begingroup$

The Busy Beaver function is usually studied for Turing machines. Of course, it's not a computable function, but for 2-state Turing machines, the first four values are known, and the fifth conjectured.

But it can be defined for any Turing-complete formal system, such as for the many cellular automata that are known to be Turing-complete. For example, Conway's Game of Life: start with a pattern in an NxN bounding box, look for patterns that end up vanishing, but take as many steps as possible to do so; BB(1)=1, BB(2)=1, BB(3)=2...

Has anyone calculated exact values or lower bounds for the first few BB values for Life or any other cellular automaton?

Improve this question
$\endgroup$
2

2 Answers 2

Reset to default
4
$\begingroup$

Your suggestion with Life sounds more like generalizing the Busy Beaver function for a fixed universal Turing machine to cellular automata. To generalize the usual Busy Beaver function (that quantifies over Turing machines with a fixed number of states), we should look at all cellular automata of some "size" and see when they "halt".

At least myself and Guillaume Theyssier have independently looked at nilpotency on all configurations as a possible way to get a nice Busy Beaver function like that. I discussed this as a kind of preamble to a talk of mine about nilpotency http://www.villesalo.com/notes/SANiCASlides.pdf (2 states, radius $\leq$ 3) and Guillaume Theyssier has done the same at http://theyssier.perso.math.cnrs.fr/castor/ (3 states, radius 1).

The definition is: Write $\mathrm{CA}_{m,n}$ for the set of cellular automata $f : A^{\mathbb{Z}} \to A^{\mathbb{Z}}$ where $A = \{1,2,...,m\}$ and $f$ admits a neighborhood of $n$ consecutive cells meaning $f(x)_i = F(x|_{\{i,i+1,...,i+n-1\}})$ for some function $F : A^n \to A$ (we can w.l.o.g. assume the neighborhood is on the right, as composing by a shift will not affect nilpotency). Now, define $$\mathrm{MND}_{m,n} = \max\{k \;|\; \exists f \in \mathrm{CA}_{m,n}: f^{k-1}(A^{\mathbb{Z}}) \neq \{0^{\mathbb{Z}}\} \wedge f^k(A^{\mathbb{Z}}) = f^{k+1}(A^{\mathbb{Z}}) = \{0^{\mathbb{Z}}\}\}$$ i.e. $\mathrm{MND}_{m,n}$ is the maximal $k$ such that some CA with neighborhood size $n$ on an alphabet of size $m$ is nilpotent at exactly step $k$.

I think this is the right candidate, because nilpotency is one of the most important undecidable problems in the theory of cellular automata.

I give the following values in my talk (with a different convention): $\mathrm{MND}(2,3) = 2$, and I give an example that does not die after $7$ steps and seems to be nilpotent, suggesting $\mathrm{MND}(2,7) \geq 7$. I have since proved (sloppily and undocumentedly) that that CA is nilpotent after $9$ steps, so indeed $\mathrm{MND}(2,7) \geq 7$.

Theyssier's record is $\mathrm{MND}(3,3) \geq 19$, for these examples we also don't know what the actual exact nilpotency time is.

Florian Bridoux showed $\mathrm{MND}((4q)^2,3) > q^q$ after a talk of mine, and also showed that $\mathrm{MND}'(2,3)$ is infinite for the variant where the neighborhood need not be contiguous.

By undecidability of nilpotency and standard embedding arguments, $\mathrm{MND}(m,n)$ grows as a busy beaver function in both variables (assuming $m \geq 2$), i.e. faster than any total recursive function.

I don't know enough about Life to answer your actual question.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I realize that your question did not perhaps have a "suggest your favorite notion of BB" component to it. Anyway, hopefully this is not too off-topic, would've put it as a comment but I had too much to say. $\endgroup$
    – Ville Salo
    Commented Aug 28, 2019 at 5:33
  • $\begingroup$ An interesting related discussion! Nilpotent=every starting configuration in that CA must eventually vanish? There is mention of this happening in k steps. But I don't see any mention of the starting configuration as an input variable. k can be arbitrarily large for a given CA by choosing a suitable starting configuration (e.g. a pair of gliders on a collision course, starting very far apart). What am I missing? $\endgroup$
    – rwallace
    Commented Aug 28, 2019 at 18:48
  • 1
    $\begingroup$ Any initial configuration is allowed in this definition. If there is a glider, the particular CA is not nilpotent and does not contribute a $k$ in the formula. There are nilpotency variants where we restrict to finite-support or periodic initial conditions but perhaps they are somewhat less important. $\endgroup$
    – Ville Salo
    Commented Aug 28, 2019 at 19:37
  • 1
    $\begingroup$ @rwallace I'll add to Ville's response that it's a classical result in cellular automata theory that if all initial configurations eventually vanish, then there exists $k \in \mathbb{N}$ such that they all vanish after at most $k$ steps. $\endgroup$
    – Ilkka Törmä
    Commented Aug 29, 2019 at 8:07
2
$\begingroup$

A closely related question is the following. Play Game of Life on an $n \times n$-torus. Since the state space is finite, every sequence of game states $s_1 \to s_2 \to \dotsb$ with non-repeating states, must be finite. For given $n$, what is the longest such sequence? The relevant sequence is A294241 in the OEIS.

Now, any sequence $s_1 \to s_2 \to \dotsb \to 0$ that eventually vanish has no repeated game states, so in particular, the sequence above is an upper bound to the type of Busy beaver function you defined.

Thus, if you allow for life on a torus (which seems more natural), the sequence $2, 2, 3, 10, 52, 91,\dotsc$ gives upper bounds to your BB function.

EDIT: After some clarification, it makes sense to define the following. Let $BB'(n)$ be the length of the longest sequence of states that eventually ends in an orbit, given an initial state confined to a $n \times n$-region. Since the empty state is an orbit, we have $BB'(n)\geq BB(n)$, where $BB(n)$ is the function defined by OP.

Improve this answer
$\endgroup$
4
  • $\begingroup$ An interesting related question! But to be clear, it is not an upper bound. The above sequence is less than 2^(N^2), whereas the BB function is very much greater. $\endgroup$
    – rwallace
    Commented Aug 28, 2019 at 18:36
  • $\begingroup$ @rwallace How is it that the BB-function you defined greater? You define it as taking as many steps as possible, then vanish. Of course, you cannot have any repeating state among the steps, as otherwise you have an infinite loop, (which wont vanish)... $\endgroup$
    – Per Alexandersson
    Commented Aug 29, 2019 at 6:05
  • 1
    $\begingroup$ @PerAlexandersson The CA is allowed to use as many cells as it wishes outside the initial pattern, the entire configuration just has to die eventually. Usually "Busy Beaver" refers to a lower semicomputable function $f : \mathbb{N} \to \mathbb{N}$ that eventually stays above any computable function (and which come from simulating a universal computation model). It is suggested in the question that simulating Life on finite-support initial configurations is a Busy Beaver type function (and surely this is true), thus it would eventually surpass the computable function $2^{N^2}$. $\endgroup$
    – Ville Salo
    Commented Aug 29, 2019 at 6:21
  • $\begingroup$ @VilleSalo Ah, yes that makes sense! I assumed that everything was happening in a bounded region. $\endgroup$
    – Per Alexandersson
    Commented Aug 29, 2019 at 6:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .