Is it alive or is it a cellular automaton.pdfVIP

4/1995 Is it alive or is it a cellular automaton?Kari ElorantaInstitute of MathematicsHelsinki University of Technology02150 Espoo, Finlandeloranta@janus.hut.fi\Organic molecules cannot be synthesized my man. (Vitalists)IntroductionEver since the fundamental contribution by von Neumann cellular automata haveenjoyed a central position in the development of ideas of arti cial life ([7]). They areat the crossing point where physical phenomena described by statistical mechan-ics and information theoretic concepts of computation meet with often surprisingresults. In this article we will make a brief excursion to this territory.1. What are they?Cellular automata (c.a.) in their purest form are deterministic rules for describingthe evolution of an array of objects. Consider the simplest set-up of a cellularautomata de ned on the one-dimensional integer lattice. Let each cell (integer site)be in one of two possible states, 0 = dead and 1 = alive. The c.a. rule is the recipehow the cells are updated based on their own and neighbors states. The same localrule is applied everywhere and the update is synchronous i.e. done simultaneouslyTitle mutated from Tom Rays \ancestor.1 for all cells in the lattice. Because of this the c.a. are in information theory calledsliding block codes; one moves e.g. a rule template like in Figure 1a over the integers(the upper rule computes the value in the grey cell based on two neighboring cellsabove, the lower according to the cell and its three nearest neighbors on both sides).If the local rule is instead de ned on a two-dimensional neighborhood we will get atwo-dimensional c.a.The key ingredients in the de nition are the locality of interaction of the cellsand the fact that the rule, the \physical law is everywhere the same. Variationsexist, e.g. one can add noise to the updating process to get a probabilistic c.a. ordo asynchronous updates. These are interesting and important but well omit themhere.Figure 1b. shows a 16 step evolution of a si