This way, Banks was able to construct very small universal 2D cellular automata.In the 70s and 80s, the study of cellular automata shifted to the one-dimensional space, motivated bythe formal study of parallel algorithmics and formal languages recognition. Using these components, under the assumptionthat the family of elements is powerful enough, one obtains a universal cellular automaton under everyreasonable hypothesis: from boolean circuits, one can wire finite state machines and memories to simu-late sequential machines like Turing machines or, one can wire finite state machines encoding the localrule of a cellular automaton and put infinitely many copies of that machine on a regular lattice, usingwires to connect and synchronize the grid of automata to simulate the behavior of the encoded cellularautomaton. Wires, gates, clocks, fan-out, signal crossing, etc are em-bedded into the configuration space of some local rule. In the 60s and 70s, universality was mainly studied for high-dimensional cellular automata (2D, 3D).In this context, it seems natural, to achieve universality, to take inspiration from real-world computersby simulating components of boolean circuits. For a detailed historical study, see the survey.
Since then, universality has been studied for itself both in the case of two-dimensional andone-dimensional cellular automata. Therefore, com-putation universality is one of the basic ingredients of self-reproducing cellular automata first introducedby von Neumann and in the subsequent works of Codd and others to achieve construction uni-versality. Universality is also a convenient tool in computationas a way to transform data, that can be further manipulated by the machine, into code. Universal machines are, in some way, the simplest type of complex machines with respect to computa-tional aspects: the sum of all possible behaviors. After an historical introduction and proper definitions of intrinsic uni-versality, which is discussed with respect to Turing and circuit universality, we discuss constructionmethods for small intrinsically universal cellular automata before discussing techniques for provingnon universality. This talk advocates intrinsic universality as a notion to identify simple cellular automata with com-plex computational behavior. Laboratoire d’informatique fondamentale de Marseille (LIF),Aix-Marseille Universit´e, CNRS,39 rue Joliot-Curie, 13 013 Marseille, France Intrinsically Universal Cellular Automata Murphy (Eds.):The Complexity of Simple Programs 2008.EPTCS 1, 2009, pp.