2009/11/15 by David Eppstein · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Physics and Astronomy · #Artificial intelligence #Automaton #Cellular Automata and Applications #Cellular automaton #Computability, Logic, AI Algorithms #Computer science #DNA and Biological Computing #Theoretical computer science #nlin.CG
paper · pdf · doi:10.1007/978-1-84996-217-9_6
published as Springer-Verlag, 2010, pp. 71-98 · 30 pages, 23 figures
arxiv created 2009/11/15 · openalex publication_date 2010/01/01 · arxiv updated 2010/09/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We propose a four-way classification of two-dimensional semi-totalistic cellular automata that is different than Wolfram's, based on two questions with yes-or-no answers: do there exist patterns that eventually escape any finite bounding box placed around them? And do there exist patterns that die out completely? If both of these conditions are true, then a cellular automaton rule is likely to support spaceships, small patterns that move and that form the building blocks of many of the more complex patterns that are known for Life. If one or both of these conditions is not true, then there may still be phenomena of interest supported by the given cellular automaton rule, but we will have to look harder for them. Although our classification is very crude, we argue that it is more objective than Wolfram's (due to the greater ease of determining a rigorous answer to these questions), more predictive (as we can classify large groups of rules without observing them individually), and more accurate in focusing attention on rules likely to support patterns with complex behavior. We support these assertions by surveying a number of known cellular automaton rules.