Demonstration of the Universality of a New Cellular Automaton
Emmanuel Sapin, Olivier Bailleux, Jean-Jacques Chabrier, Pierre Collet · 2007
This paper make a contribution to the theory of cellular automata. In this theory, a central issue is classification and search of universality of cellular automata. The problem of search of universality is asked by Wolfram in Twenty Problems in the Theory of Cellular Automata by the question ”How common are computational universality and undecidability [are] in cellular automata?”. This paper describes how universal automata can be sought and found using evolutionary algorithms. A demonstration showing that a new automaton (called R) can implement the Game of Life (which is universal in the Turing sense) is described. All the elements of the evolutionary algorithms that were used to find R are provided for replicability, as well as the analytical description in R of a cell of the Game of Life.