Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We can draw a parallel between cellular automata and busy-beaver numbers. For example the initial case occupies some kxk square in the plane,leaving all the other cells emty, after how many generations we this will come to some predefined state.(analogue with game of life) We call busy-beaver number in this case the number of generations, before we come to this state. Is busy-beaver sequence in this case computable?

share|improve this question

closed as not a real question by Andres Caicedo, Chris Eagle, Davide Giraudo, Ross Millikan, Thomas Feb 16 '13 at 18:52

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

    
What is the Game of Life? What is a busy-beaver sequence? –  Chris Eagle Feb 16 '13 at 17:19
    
1  
I do not understand the question. How do you define the busy-beaver for the Game of Life? –  Andres Caicedo Feb 16 '13 at 17:20
    
4  
As written, your question makes no sense. Please check the definitions in the links you provided. –  Andres Caicedo Feb 16 '13 at 17:23
show 6 more comments

1 Answer 1

I am not an expert on computability theory or cellular automata, but: reading your description literally, I don't find it to be a good analogy to busy beaver numbers for Turing machines.

The usual busy beaver function $B$ ranges over a class of different $n$-state Turing machines and outputs the largest number $B(n)$ such that an $n$ state Turing machine (say, which can write $0$ or $1$), when given an infinite string of $0$'s, outputs a string of $B(n)$ consecutive $1$'s and then halts.

Now, given a $2$-dimensional cellular automaton $C$ -- I assume this means that there is some uniform decision rule for a square's having $0$ or $1$ in the next generation given its current value and the values of the $8$ adjacent squares -- it makes sense to ask what happens when you start it with a $k \times k$ square of $1$'s. We can ask for the number of generations before we reach an empty grid (all $0$'s), if this number exists; maybe we define it to be $\infty$ if it never reaches the empty state. (Note that in the classical busy beaver we count the size of the output rather than the amount of time until halting, but so far as I know this is not a critical difference.)

You then get a function $C$ from $\mathbb{Z}^+$ (positive integers) to $\mathbb{Z}^+ \cup \infty$. This function does not seem very similar to the classical busy beaver function, but one can still ask whether it is computable: note that this is a different question for each cellular automaton $C$.

It is clearly computable for some cellular automata, e.g. the one which turns every cell to $0$. Some simple experimentation -- e.g. at this site -- shows that taking $C$ to be the Game of Life, the function is (not only computable but) extremely simple: $C(1) = 1$, $C(3) = 3$, otherwise $C(k) = \infty$.

There are only finitely many cellular automata according to the above definition, so one could explore each of them individually and, perhaps, decide whether the above function is computable. Is that your question?

share|improve this answer
    
A fairly good analogue to BB would be to ask, "what is the maximal time until empty grid among all starting configurations that fit within an $k\times k$ square and do reach an empty grid?" –  Henning Makholm Nov 8 '13 at 0:34
    
... That is almost certainly uncomputable for the standard Game of Life: Given the kinds of things people are making in Life, it should be a simple matter of engineering to build a Turing machine there, with puffers to extend a tape in both directions while the machine works. The most difficult thing would probably be to make it self-destruct completely after it reaches a halting state, but given that the Gemini spaceship does self-destruct after having replicated itself it seems unlikely that there wouldn't be a way to make a self-destroying Turing machine. –  Henning Makholm Nov 8 '13 at 0:36
    
Alternatively, one could ask, "what is the maximal population size for a starting configuration that fits within a $k\times k$ square and doesn't grow without bounds?" Then the Turing machine simulation would only have to stop when it stops, not to destroy itself. –  Henning Makholm Nov 8 '13 at 0:39
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.