 |
    |
A New Universal Cellular Automaton Discovered by Evolutionary Algorithms
Emmanuel Sapin1, Olivier Bailleux1, Jean-Jacques Chabrier1, and Pierre Collet2
1Université de Bourgogne, 9 av. A. Savary, B.P. 47870, 21078 Dijon Cedex, France
emmanuelsapin@hotmail.com
olivier.bailleux@u-bourgogne.fr
jjchab@u-bourgogne.fr
2Laboratoire d’Informatique du Littoral, ULCO, Calais, France
Pierre.Collet@Univ-Littoral.Fr
Abstract. In Twenty Problems in the Theory of Cellular Automata, Stephen Wolfram asks “how common computational universality and undecidability [are] in cellular automata.” This papers provides elements of answer, as it describes how another universal cellular automaton than the Game of Life (Life) was sought and found using evolutionary algorithms. This paper includes a demonstration that consists in showing that the presented R automaton can both implement any logic circuit (logic universality) and a simulation of Life (universality in the Turing sense).
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 Life.
LNCS 3102, p. 175 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004