Demonstration of the Universality of a New Cellular Automaton
E. Sapin, O.Bailleux, J.-J. Chabrier, and P. Collet
The paper deals with classification and search for universality of cellular automata —one of the central issues of cellular automata theory. The problem of search for universality was posed by Wolfram in Twenty Problems in the Theory of Cellular Automata —“How common are computational universality and undecidability [are] in cellular automata?”. We demonstrate how universal automata can be designed and found using volutionary algorithms. Namely, we show how to volved a new automaton (called R) that can implement the Game of Life (which is universal in the Turing sense). All elements of the volutionary algorithms that were used to and R are provided for replicability, as well as the analytical description of representing a cell of the Game of Life in cellular automaton R.