RULE 110: UNIVERSALITY AND CATENATIONS

Abstract. Cellular automata are a simple model of parallel computation. Many people wonder about the computing power of such a model. Following an idea of S. Wolfram [16], M. Cook [3] has proved than even one of the simplest cellular automata can embed any Turing computation. In this paper, we give a new high-level version of this proof using particles and collisions as introduced in [10]. Introduced in the 40s by J. Von Neumann as a parallel model of computation [13], cellular automata consist of many simple entities (cells) disposed on a regular grid. All cells evolve synchronously by changing their state according to the ones of their neighbours. Despite being completely known at the local level, global behavior of a cellular automaton is often impossible to predict (see J. Kari [6]). This comes from the fact that even “simple” cellular automata can exhibit a wide range of complex behaviors. Among those behaviors, one often refers as emergence the fact that “complexity ” of the whole system seems far greater than complexity of its elements. Elementary cellular automata are an example of subclass of “simple ” cellular automata. They are obtained by considering only a one dimensional grid (i.e., a line of cells), tw