Homepage Alexander Schatten - Information / Tutorials  Homepage Alexander Schatten - Information / Tutorials  HomeContact/CVInformation/TutorialsLehre/ForschungMain InterestsSoftwarePublicationsImages > Home > Information / Tutorials > Cellular Automata TutorialPrinter FriendlyIntroductionA Glance at Dynamical Systems and Chaos or "A new Science named Complexity"Building Cellular AutomataThe CellThe LatticeNeighbourhoodsApplying RulesMathematics...SummaryThe Behaviour of CA'sUniversality and the Turing-StuffClassesOn the Edge of ChaosApplicationsGame of LifeBilliard / HPP, FHP - Gas ModelsIsing ModelSelf-ReproductionFurther ExamplesCellular Automata vs. Differential EquationsIn the Background, a more Philosophical ApproachThe "Beauty" of Physical LawsFeynman's ExampleModelingReferencesPrint ReferencesInternet LinksAnd now to something completly different...Cellular Automata Tutorial 1. Introduction From the theoretical point of view, Cellular Automata (CA) were introduced in the late 1940's by John von Neumann (von Neumann, 1966; Toffoli, 1987) and Stanislaw Ulam. From the more practical point of view it was moreless in the late 1960's when John Horton Conway developed the Game of Life (Gardner, 1970; Dewdney, 1989; Dewdney, 1990). CA's are discrete dynamical systems and are often described as a counterpart to partial differential equations, which have the capability to describe continuous dynamical systems. The meaning of discrete is, that space, time and properties of the automaton can have only a finite, countable number of states. The basic idea is not to try to describe a complex system from "above" - to describe it using difficult equations, but simulating this system by interaction of cells following easy rules. In other words: Not to describe a complex system with complex equations, but let the complexity emerge by interaction of simple individuals following simple rules. Hence the essential properties of a CA are a regular n-dimensional lattice (n is in most cases of one or two dimensions), where each cell of this lattice has a discrete state, a dynamical behaviour, described by so called rules. These rules describe the state of a cell for the next time step, depending on the states of the cells in the neighbourhood of the cell. The first system extensively calculated on computers is - as mentioned above - the Game of Life. This game became that popular, that a scientific magazine published regularly articles about the "behaviour" of this game. Contests were organized to prove certain problems. In the late 1980's the interest on CA's arised again, as powerful computers became widely available. Today a set of accepted applications in simulation of dynamical systems are available. top 2. A Glance at Dynamical Systems and Chaos or "A new Science named Complexity" Nature and Nature's Law lay hid in night, God said, let Newton be! and all was light! This proposed epitaph from Alexander Pope for Isaac Newtons grave shows the mental attitude of the 19th century. Since the beginning of the 20th century the scientific community had to dismiss (with a heavy heart) the idea of the capability to calculate the future state of a physical system exactly if the current state of the system is known with a high precision. This idea is called in a more philosophical terminology the Laplacian Demon, refering to an ideal demon, knowing precisely the current state of a system, must be able to foresee the exact development of this system. In the back of the mind was the believe, that small errors in analysation of the current system will cause small errors in extrapolation of future development of the system.) I want to point out that these ideas had to fall regarding a few selected milestones, that show the necessity for the change of the paradigm: Henri Poincare and the "solution" of the 3-body problem Edward Lorenz problem of weather forecast Werner Heisenberg and the uncertainty relation Oscar II the Swedish king, who was very interested in mathematics founded a price won by Poincare proofing, that there is no closed form mathematical solution for this problem. (Besides: The article of Poincare was that chaotic, that a printed and partially sold circulation has to be reprinted, as the last changes from Poincare arrived that late. This reprint has to be paid by Poincare, so that the sum he received from Oscar II was more than spent. The contact of Lorenz to chaotic systems occurred in doing weather forecasts. To tell it in few words: trying different models (and trying to speed up the calculations) Lorenz reduced the precision of one parameter, thinking, that this will lead in little reduced accuracy in the result of the calculation. The astonishing outcome was a completely different result! A consequence both men draw is, that complex dynamical systems often show huge effects on small changes in the starting conditions. Werner Heisenberg supplements the finding, that it is impossible to measure the position and speed of a particle with high precision at the same time. This cognition is one of the basis bricks of the quantum theory. Putting the results of Lorenz and Poincare together with the uncertainty relation Heisenberg's one can see clearly, that the Laplacian Demon has lost it's right to exist. This was a shock for most of the scientists. New attempts to the understanding of complex dynamical systems were necessary. With the work of Benoit Mandelbrot the new science of fractal (broken) dimensions and chaos started, recently a more unified approach called the science of complexity emerged. Trying to give a definition of complexity shows the difficult situation this new branch stucks in. The physicist Seth Lloyd from the MIT found that more than 30 different definitions of Complexity exist. Nevertheless a definition from Christopher Langton from SantaFe Institute seems to be essential, describing Complexity as the science trying to describe the states on the edge of chaos. In other words, he assumes, that order emerges from systems on the edge of chaos. In more general terms one can pose the question: "How arises order from chaos?". As there are a lot of different streams in chaos and complexity research, it is not the space here to discuss these interesting developments in detail. I just felt the necessity to get into touch with these items. For more serious introductions I can recommend McCauley (1993) and Ott (1994). top 3. Building Cellular Automata 3.1 The Cell The basic element of a CA is the cell. A cell is a kind of a memory element and stores - to say it with easy words - states. In the simplest case, each cell can have the binary states 1 or 0. In more complex simulation the cells can have more different states. (It is even thinkable, that each cell has more than one property or attribute and each of these properties or attributes can have two or more states.) 3.2 The Lattice These cells are arranged in a spatial web - a lattice. The simplest one is the one dimensional "lattice", meaning that all cells are arranged in a line like a string of perls. The most common CA's are built in one or two dimensions. Whereas the one dimensional CA has the big advantage, that it is very easy to visualize. The states of one timestep are plotted in one dimension, and the dynamic development can be shown in the second dimension. A flat plot of a one dimensional CA hence shows the states from timestep 0 to timestep n. Consider a two dimensional CA: a two dimensional plot can evidently show only the state of one timestep. So visualizing the dynamic of a 2D CA is by that reason more difficult. By that reasons and because 1D CA's are generally more easy to handle (there is a much smaller set of possible rules, compared to 2D CA's, as will be explained in the next section) first of all the one dimensional CA's have been exploited be theoreticians. Most theoretical papers available deal with properties of 1D CA's. 3.3 Neighbourhoods Up to now, these cells arranged in a lattice represent a static state. To introduce dynamic into the system, we have to add rules. The "job" of these rules is to define the state of the cells for the next time step. In cellular automata a rule defines the state of a cell in dependence of the neighbourhood of the cell. Different definition of neighbourhoods are possible. Considering a two dimensional lattice the following definitions are common: von Neumann Neighbourhood four cells, the cell above and below, right and left from each cell are called the von Neumann neighbourhood of this cell. The radius of this definition is 1, as only the next layer is considered. Moore Neighbourhood the Moore neighbourhood is an enlargement of the von Neumann neighbourhood containing the diagonal cells too. In this case, the radius r=1 too. Extended Moore Neighbourhood equivalent to description of Moore neighbourhood above, but neighbourhood reaches over the distance of the next adjacent cells. Hence the r=2 (or larger). Margolus Neighbourhood a completely different approach: considers 2x2 cells of a lattice at once. for more details take a look at the Applications  von Neumann Neighbourhood  Moore Neighbourhood  Extendend Moore Neighbourhood The red cell is the center cell, the blue cells are the neighbourhood cells. The states of these cells are used to calculate the next state of the (red) center cell according to the defined rule. As the number of a cells in a lattice has to be finite (by practical purposes) one problem occurs considering the proposed neighbourhoods described above: What to do with cells at borders? The influence depends on the size of the lattice. To give an example: In a 10x10 lattice about 40% of the cells are border cells, in a 100x100 lattice only about 4% of the cells are of that kind. Anyway, this problem must be solved. Two solutions of this problem are common: Opposite borders of the lattice are "sticked together". A one dimensional "line" becomes following that way a circle, a two dimensional lattice becomes a torus. the border cells are mirrored: the consequence are symmetric border properties. The more usual method is the possibility 1. 3.4 Applying Rules An example of "macroscopic" dynamic resulting from local interaction is "the wave" in a - say soccer-stadium. Each person reacts only on the "state" of his neighbour(s). If they stand up, he will stand up too, and after a short while, he sits down again. Local interaction leads to global dynamic. One can arrange the rules in two (three) classes: every group of states of the neighbourhood cells is related a state of the core cell. E.g. consider a one-dimensional CA: a rule could be "011 -> x0x", what means that the core cell becomes a 0 in the next time step (generation) if the left cell is 0, the right cell is 1 and the core cell is 1. Every possible state has to be described. "Totalistic" Rules: the state of the next state core cell is only dependent upon the sum of the states of the neighbourhood cells. E.g. if the sum of the adjacent cells is 4 the state of the core cell is 1, in all other cases the state of the core cell is 0. "Legal" Rules: a special kind of totalistic rules are the legal rules. As it is not of advantage in most cases to use rules that produce a pattern from total zero-state lattices (all cells in the automaton are 0), Wolfram defined the so called legal rules . These rules are a subset of all possible rules, a selection of rules that produce no one's from zero-state lattices. Case 1 shows why one-dimensional automata are that popular in theoretical studies. if only the left, the right neighbour and the cell itself is considered in the rules (r=1), there are 256 possible rules totally: 2 3=8 possible states for three binary digits, each of these 8 states can produce a 1 or a 0 for the center cell in the next generation. Hence 28=256 rules are existing. So in general terms the number of rules can be calculated by k^(k^n), where k is the number of states for the cell and n is the number of neighbours (including the core cell itself). So we can easily see, that for a two-dimensional CA with Moore neighbourhood, 2 states and r=1 follows k=2 and n=9. So 2^(2^9) = 2^512 = approx. 10^154 possible rules exist. A comprehensive study of all rules in higher dimensional automata is thus not easily possible. Another important variation are the reversible cellular automata. The "only" difference to the CA's described above is, that the time development of the system is completely reversible. That means, that at any time-step of the development the rules allow to go forward or back in time without losing any information. 3.5 Mathematics... 3.5.a Introduction I want show possible mathematical formulations of essential parts of the cellular automata theory in this section. It is not the purpose of this chapter to develop a comprehensive mathematical framework on this topic. A more detailed review and some hardcore mathematics, some more theoretically founded introductions, respectively, you can find in: Vichniac G.Y., 1984: Physical modeling, containing symmetry properties, reversible rules, Ising model, non-ergodicity and order parameters, period doubling Margolus N., 1984: Modeling Physics with reversible cellular automata, good introduction to reversibility of CA's. Wolfram S., 1984: From one of the "inventors" Stephen Wolfram about universality and complexity in CA's, the classification of one-dimensional automata into four classes and their properties Grassberger P., 1984: from the "chaos guru" Grassberger: aspects and correlation of CA's with chaos theory Willson S.J., 1984: growth rates and fractal dimensions 3.5.b Cell-Space, Neighbours and Time Let us define the cell-space as  , where i, j are the number of column/row of the lattice with the maximum extent of n columns and m rows. Let  be the definition of the Moore neighbourhood. (Other neighbourhood definitions are similar. E.g. for the Extended Moore neighbourhood you have to replace the <= 1 with <= 2). Consider (as it is easier to understand) a one dimensional cellular automaton with two possible states for each cell, in mathematical terms  , and totalistic rules, meaning, that the next state of each cell depends only on the sum of the states of the adjacent cells. So the state of cell zi for the next timestep (t+1), one could define the totalistic rule as  meaning that the state of the core-cell zi becomes 1 if the sum of the neighbourhood cells including the core-cell is  , 0 otherwise. To write this formula for the two dimensional automaton is not very different from this formulation and will be done in the examples section describing the Game of Life. 3.5.c Legal Rules A striking restriction of all possible rules to so called legal rules was introduced be Wolfram. The idea is: from the total zero-state - the state of all cells is 0 may not emerge any development - no 1 may appear in any cell! Consider a one-dimensional CA with two states and two neighbours on each side. 32 totalistic legal rules are existing (out of 1024 possible rules totally). It is possible to assign a definite number to each possible legal rule. These code-numbers can be derived as follows:  , where the function f is defined as  Now a code for all legal rules can be calculated by  In the case of an automaton as described above, to all 32 legal rules one can assign a definite Code C f containing all even numbers from 0 to 64. 3.5.d Reversible Automata A reversible automaton is a system, that looses no information in proceeding in time. So at any point in the timescale, the system is fully reversible. To introduce a reversible automaton we have to extend the former definition of dynamical time development z(t+1) = f(z(t), Nz(t)) to z(t+1) = f(z(t), Nz(t)) - z(t-1). (One has to take care, that z(t+1) doesn't leave the defined set of states e.g. between 0..(n-1) by calculating the difference modulo 2). To "turn round" the direction of time, hence to calculate z(t-1) out of z(t) one simply has to use the formula. z(t-1) = f(z(t), Nz(t)) - z(t+1). The function (rule) f is arbitrary. So one has an easy possibility to create reversible CA's out of a broad set of rules. 3.6 Summary The general properties of cellular automata are: CA's develop in space and time a CA is a discrete simulation method. Hence Space and Time are defined in discrete steps. a CA is built up from cells, that are lined up in a string for one-dimensional automata arranged in a two or higher dimensional lattice for two- or higher dimensional automata the number of states of each cell is finite the states of each cell are discrete all cells are identical the future state of each cell depends only of the current state of the cell and the states of the cells in the neighbourhood the development of each cell is defined by so called rules It has to be noticed, that the definitions above are of a very conventional type. One shall not limit to these propositions! A lot of useful extensions are proposed already, and thinkable in general. More about further developments can be found in the Applications section. top 4. The Behaviour of CA's 4.1 Universality and the Turing-Stuff A system that is capable to do universal computation is able to perform any finite algorithm. Only a CA calculating for an infinite period of time can be universal. 4.2 Classes "...many (perhaps all) cellular automata fall into four basic behaviour classes.", Stephen Wolfram (Wolfram, 1984). Wolfram gives a rough geometrical analogy of behaviour of these four classes: Class 1 - limit points Class 2 - limit cycle Class 3 - chaotic - "strange" attractor Class 4 - more complex behaviour, but capable of universal computation Class 1 cellular automata After a finite number of time-steps, class one automata tend to achieve an unique state from (nearly) all possible starting conditions. Class 2 cellular automata This type of automata usually creates patterns that repeat periodically (typical with small periods) or are stable. One can understand this type of CA's as a kind of filter, which makes them interesting for digital image processing Class 3 cellular automata From nearly all starting conditions, this type of CA's lead to aperiodic - chaotic patterns. The statistical properties of these patterns and the statistical properties of the starting patterns are almost identical (after a sufficient period of time). The patterns created by this type of CA's (usually one dimensional CA's) are a kind of self-similar fractal curves. Class 4 cellular automata After finite steps of time, this type of CA's usually "dies" - the state of all cells becomes zero. Nevertheless a few stable (periodic) figures are possible. One popular example of an automaton of this type is the Game of Life. In addition to that Class 4 automata can perform universal computation This class of CA's show a high irreversibility in their time development. The first three types can be read as Cantor sets with a certain dimensionality, either in countable or in fractal dimension. Class 3 is the most frequent class. With increasing k and r the probability to find a class 3 automaton for an arbitrary selected rule is again increasing. 4.3 On the Edge of Chaos Christopher Langton introduced the term "On the Edge of Chaos" with the intention, that this is the most "creative" state of a dynamical system. A permanent flickering between order and chaos. In most non-linear systems one can detect a parameter that is responsible for the transition from order to chaos. To give an example: consider a water tap that is leaking. The parameter defining the state of the system (order-chaos) is evidently the flow-rate of the water. Langton tried to detect this parameter in cellular automata systems. To cut a long story short: He found an equivalent parameter for CA's:  . is the probability that a cell will be alive in the next generation, with a maximum of 0,5. (Values over 0,5 would lead to an inverted system) Let's discuss the possible values: Behaviour 0 No development. All cells die in the next step. near 0 not much action. all cells die within a short period of time slightly higher typical class 2 behaviour - periodic patterns are occurring 0 << < 0,3 the higher the parameter, the longer takes the stabilization of the class 2 patterns "critical" point round 0,3 class 4 automata! near 0,5 class 3 With this new schema, Wolfram's classes receive a new meaning in the theory of CA behaviour. To repeat the important idea of Langton: below this certain value (in this case about 0,3) the system is too simple - as there is too much order - to be creative. Other extremes are too chaotic to find structures or destroy any structure. In his opinion only around this certain point - Langton calls it "in the edge of chaos" - real life is possible. top 5. Applications 5.1 Game of Life The Game of Life (GOL) was one of the first "applications" showing that cellular automata are capable of producing dynamic patterns and structures. The GOL is "plays" on a two dimensional lattice with binary cell states, Moore neighbourhood and arbitrary border conditions. To be vivid: a 1 can be interpreted that the cell is "living", a 0 that the cell is "dead". John Horton Conway introduced the set of rules as described below: a cell that is dead at the time step t, becomes alive at time t+1 if exactly three of the eight neighbouring cells at time t were alive. a cell that is alive at time t dies at time t+1 if at time t less than two or more than three cells are alive. Though these rules seem to be (are !) rather simple, vivid life can establish following this dynamic. A set of often occurring patterns have been described, some are flickering infinitely between two states like blinkers, some are static blocks, snakes, ships,..., others are moving over the lattice and vanish into infinity of the lattice. One example are the "famous" glider figure, whose dynamic is shown in the figure below. Also so called glider-guns are existing, that fire for an infinite period of time such gliders. A lot of different dynamic has been described and tested. E.g. the pattern that occurs if two gliders are colliding. These gliders for example can be used as signals instead of electric impulses and "computers" can be built within these rules...  Glider By the way, meanwhile a lot of variations of these classic rules and some new rules exist. If you are interested in this fascinating game take a look at Dewdney (1990), Gerhart (1995), Gardner (1970, 1983), Hayes. 5.2 Billiard / HPP, FHP - Gas Models For less playful, but more realistic customers, the dynamic of cellular automata can be used to simulate the behaviour of gas - particles. These automata have to be constructed (in contrast to the game of life) as reversible automata (as a gas particle may e.g. hardly disappear from the lattice). The construction of a gas model is similar to the so called billiard automaton, so the principles is described together in this section. In contrary to the Life automaton, the rules base on 2x2 parts of the lattice. This system is also called the Margulos Neighbourhood. A selection of rules can be: o|. .|. o|. .|o o|. .|o -+- --> -+- -+- --> -+- -+- --> -+- and so on... .|. .|o o|. .|o .|o o|. where the "o" stands for a particle (or a billiard ball) and a "." stands for an empty cell. After applying the rule and proceeding to the next time step, the 2x2 raster is moved for one block diagonally. Hence the movement of a particle needs two time-steps. If this description is a little hard to imagine take a look at the animated example below:  HPP-Gas simulation of collision of two particles This example shows the collision of two particles or billiard balls if you like it. Already this simple HPP (Hardy, de Pozzis, Pomeau)-gas model is coming close to the results of the Navier-Stokes equation, but even more details models have been introduced like the FHP (Fritsch, Hasslacher, Pomeau) model, that allows movements of particles to six directions instead of only four. The FHP-gas model can be used for example to simulate aerodynamics. For more information read: Gerhart (1995), Lim (1988), Xiao-Guang Wu (1994). 5.3 Ising Model A little different application is the CA- Ising model, that can be used to simulate ferro-magnetism. Every cell stands for the spin of a small magnet, where the state 1 may represent an "up" vector and the state 0 the "down" vector. The orientation of the spin is variable and depending on the local neighbourhood, where two conditions can be named: Temperature T > Curie-temperature: the "influence" of the second sentence ????? of thermodynamics is dominating "creating" disorder (chaos). T < Curie T.: the force between the spins is dominating and spins tend to build order CA's can be used to simulate this system, with the additional difficulty, that the spin (energy) of the whole system has to be a constant. More information can be found in Gerhart (1995), Hayes, Doolen (1991), Toffoli (1987). 5.4 Self-Reproduction An essential "property" of life is self-reproduction. Scientists on the SantaFe Institute, especially Christopher Langton worked on this topic, so I want to explain in short words Langton's proof, that cellular automata are capable to produce self-reproducing patterns (loops to be precise) (e.g. Langton, 1984): Historically John von Neumann posed the question, whether a self-reproducing machine is existing, or in more detail, what kind of logical organisation of an automaton is sufficient to produce self-organisation. His approach to this problem was a classical logic-mathematical one. The result of his theoretical deduction is, that an universal Turing machine embedded in a cellular array using cells with 29 states and a neighbourhood with 5 cells is existing. This machine is called a universal constructor, and is capable to construct any machine described on the input tape and reproduce the input tape and construction machinery. To be exact, this system consists of two "layers": The cellular automaton The universal constructor inside this automaton Because John von Neumann (1903-1957) died too early, he didn't publish his system himself, but his friend and colleague Arthur W.Burks after his death (Burks, 1968). E.F.Codd (Codd, 1968) tried to show a possibility to reduce the complexity of von Neumanns automaton and introduced a machine requiring only 8-states per cell capable of self-reproduction. This machine works in a similar matter as the von Neumann design. Christopher Langton and others discussed the general problem of how to define the property "self-reproduction", to exclude trivial systems, but avoid a too restrictive definition: the key problem is the demand on universal construction. This demand is not fulfilled by natural systems (Think of patterns on animal furs for example. The biochemical proceeding is able to create the patterns on a jaguar's fur, but surely not capable of universal construction...). "It seems clear, that we should take the 'self' of 'self-reproduction' seriously, and require of a configuration that the construction of the copy should be actively directed by the configuration itself." (Langton), not in the first order by the "physical properties", the rules of the automaton. In the following figure I want to show the self-reproduction scheme presented by Codd. The basic structure is a so called data-path, containing a string of cells - core cells (in the figure below in the state 2) - surrounded by sheath cells (state 1). 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 Instead of the series of "1's" one can substitute these cells by "command"-states e.g. by a "7 0" signal. The dynamic behaviour is then: time t: t+1: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 0 7 1 1 1 1 1 1 1 1 -> 1 1 1 1 0 7 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 Now let's extend this schema with a T-junction. We can see, that the moving code sequence is duplicated at the junction point: t: t+1: 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 1 1 1 1 0 7 1 1 1 1 1 1 1 1 1 1 1 1 0 7 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 t+2: t+3: 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 7 2 2 2 2 2 2 2 7 2 2 2 2 2 2 2 2 2 2 2 2 0 2 2 2 2 2 2 1 1 1 1 1 1 0 7 1 1 1 1 1 1 1 1 1 1 1 1 0 7 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 Another important property of this machine is the path-extension. The next figure shows the path extension of a capped data-path with the command "7 0 1 1 6 0 " 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 0 6 1 1 0 1 1 1 1 2 -...-> 1 1 1 1 1 0 6 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 -...-> 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 One further "figure" has to be explained: The periodic emitter. This very important pattern can be used to produce a timer signal or to store data. With the understanding of the two previous explained figures the function should be clear: 2 2 2 2 2 2 2 0 1 1 1 1 1 2 2 7 2 2 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 2 2 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 0 7 1 1 1 1 1 1 1 1 0 7 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 and the path extension machine: 2 2 2 2 2 2 2 0 1 1 6 0 1 2 2 7 2 2 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 2 2 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 0 6 1 1 0 7 1 1 1 1 0 6 1 1 0 7 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 The information is infinitely stored in the upper cycles, and the path-extension machine creates an infinite sequence. The code used by Codd has the advantage to be capable of universal construction. But as explained above the restrictions Langton described stay. So Langton simplified to codeset with the result, that the new machines are not longer capable of universal construction, but it is possible to code longer programs within a cycle. (In Codd's schema there is not enough room in a loop to store information to construct a self-reproducing loop.) For example: instead of the "7 0 - 6 0" code, Langton uses the sequence: "7 0" With the new code-set described in detail in Langton (1984) it is easily possible to create self-reproducing loops and even populations of loops, but the principle stays the same. To comprise the results achieved by Langtons modification: the loops created with the new rules are in contrast to the von Neumann or Codd rules simple structures Langton proofed, that universality is a sufficient, but not a necessary condition for self-reproduction though simple, the loops are capable of not trivial reproduction employing both transcription and translation 5.5 Further Examples "Chemical Waves" - Belusov-Zhabotinsky Reaction Cellular Automata can even be used to model chemical waves or chemical structures like the ones created by Belusov-Zhabotinsky reaction. For more information read Gerhart (1989), Winfree (1974). Reaction-Diffusion Systems An important improvement is the introduction of cellular diffusion by Toffoli and Margolus. Consider the Margolus neighbourhood as described in the gas-modeling section. Diffusion is simulated be rotation of the 2x2 cell block by 90 degree clockwise or counter-clockwise (selection is randomized). Chopard (1993), Grassberger (1994), top 6. Cellular Automata vs. Differential Equations "Contraria non contradictoria sed complementa sunt", Niels Bohr It is impossible to give a mathematical "introduction" to differential equations in this framework, I have to refer to common mathematical primers. I want to discuss the motives why differential equations are popular in science here instead. Furthermore I will try to point out the differences compared to cellular automata. Differential Equations look back to a long history. Names like Bernoulli, Euler, Gauß, Langrange, Laplace, Poisson are close related to the development of this mathematical theory. A successful tradition of about 300 years can not be easily neglected, particularly because the ascent of modern physics is part of this story. Especially the later developed partial differential equations are significant for modern physics. In addition to that, the property of continuity, that these equations offer was corresponding to the philosophy - to the paradigm of that time. An example could be the heat equation (Toffoli, 1984):  No wonder that physicists prefer using DE's up to now, as physics is written in the words of DE and a large experience for their symbolic integration exists. This was evidently a big advantage at times, calculations had to be performed by hand. Today as the calculation in mathematics is done by computer and acception of numerical computation is increasing in the past 40 to 50 years we have to check the applications of differential equations again. Furthermore there is the problem that most differential equations have no closed form solution (especially the equations of practical relevance)! To solve certain differential equations, one gives up the symbolic calculation and does numerical approximations. Generally the way to solve these equations can be comprehended as differential equations are forced to discrete space and time the resulting power series are truncated the real - continuous variables are transformed now to discrete memory structure of a computer One of the well known CA-scientists Tommaso Toffoli contributed to this problematic (Toffoli, 1984): "... in modeling physics with the traditional approach, we start for historical reasons ... with mathematical machinery that probably has much more than we need, and we have to spend much effort disabling these 'advanced features' so that we can get our job done in spite of them." On the other hand, it is very difficult to produce quantitative results with cellular automata without losing the simplicity and vividness of rules (which seems to be an important advantage of this method). Likewise the finding of rules is often very intuitive and sometimes difficult and the number of rules is finite. But one has to regard, that though the number of differential equations is infinite, the set of equations we can write down is countable, and the set of equations we can definitely solve is very small. Refering to Niels Bohr's citation at the beginning (though related to the complementary principle in quantum physics): "Opposites don't contradict, but complement each other" my conclusion is, that (for the moment) both methods have their right to exist. One method can stimulate the other with it's results. Now we should try to exploit the possibilities of discrete numerical methods (as cellular automata are). We should not put our energy into the dispute which method is better, but in development of the methods. Future will show, which method will be superior - or even if actually one is superior. top 7. In the Background, a more Philosophical Approach 7.1 The "Beauty" of Physical Laws Paul Adrien Maurice Dirac introduced the idea, that a physical law has to be of mathematical beauty (Dirac 1963; Neuser, 1996). Though he was probably the first formulating this, in my opinion the whole concept of modern science is based on this theory. From the philosophical point of view Ernst Mach talked about science beeing a very pragmatic kind of economy of thinking. But this idea didn't explain the process of thinking and cognition, but was some kind of a basis of the evolutionary theory of cognition (see Mach 1905, 1910; Riedl 1985; Lorenz 1993). In my opinion it seems to be a wise conception to try to bring esthetics into science as humans tend to simplify complex systems for better understanding. Cellular automata can be understood as a way to simulate complex systems by constructing an esthetic - "beautiful" and easy to understand model. But in this whole discussion of beauty we should not mix up models with reality. Nobody can finally determine if nature is simple in terms of human understanding, or if we are simply so much restricted in our cognition and capability that we can not go beyond construction of simplified pictures and views of nature. 7.2 Feynman's Example In an often cited example the famous physicist Richard P.Feynman explained, that watching a chess game, complex behaviour can emerge out of a system that is limited or pressed into fixed rules. Just on the basis of these rules the whole system can evolve. This situation can be compared to natural systems. Nevertheless I am not very content with this example. Too many problems start with telling this story: Maybe the most important factor is, that the game chess has a destination, the "killing" of the hostile king. Compared with nature, this would lead to a teleologic point of view, most scientists would deny today (me too). The game is played by two men, though on the basis of the rules, but - following point 1. - with a plan in their minds. Even considering computers playing the game doesn't change this situation significantly. What do simplicity, complexity, order or disorder mean in terms of a chess game? There is no "meta- meaning" in this system. All meaning comes from the destination to win. This is very different to natural systems, where this "meta-meaning" is often understood watching the next layer e.g. the meta-meaning of atoms can be understood in terms of molecules, and so on. I believe we have to distinguish these points, otherwise we may run into danger creating specious arguments. 7.3 Modeling From my (radical constructivistic) point of one could call the discussion if a continuous model (differential equation) is superior over a basic discrete system (cellular automaton) as beeing obsolete. We could consider a simple pragmatic view for this dispute. This discussion of model-philosophy shall happen, but for practical work it is not necessary. In some cases cellular automata show high performance in modeling, in other cases one will love the high precision of quantitative estimation resulting from differential equations. So we can reduce the question on the parallelity of model and nature. This problem on the other hand is essential and may not be ignored. A cellular automata simulation gives good results - corresponding with analysis of the "nature" of some system. May we conclude now, that the "real" system is behaving like our automaton? I guess spontaneous most readers would answer: "Evidently not!". But do we ask this question also for other physical models? Some differential equation or more generally, one deduced law from quantum mechanics correlates with the observation made, the scientific community follows that the theory is correct. By the way: the machines to make these observations - e.g. scanning tunnel microscopes, CERN, ... - are built on the basis of the model, whose deduction I want to prove. I don't want to discredit quantum mechanics - I even wouldn't have the genius to do so - but I believe we should put the question more often if we probably do circular proves! Let's keep this in mind if we enthusiasts of new methods - in this case cellular automata - do interpret results (see also Popper, 1934). If we try to achieve too much with one step, we take the risk to discredit the whole method - as conventional scientists will call us (with some right) unserious. My own opinion is, that the shift of the paradigm at the beginning of this century to a view into a "discrete world" is not closed yet. In many areas we do "modern" - discrete - science with "old" - continuous - methods. No wonder, because continuous methods have margin of 250 years. But the second part of the shift - the change in mathematical modelling and scientific method was introduced with the radical changes the microcomputers brought. As I believe in the ideas of Thomas Kuhn (Kuhn, 1970)it is common for shifts in paradigmata we will have to be patient yet. top 8. References 8.1 Print References Burks A.W. (1968), ed, Essays on Cellular Automata, Univ. of Illinois Press, Illinois Chopard B. (1993), Droz M., Study of the A+B to C reaction-diffusion process, International Journal of Modern Physics C, 4, 209-215 Codd E.F. (1968), Cellular Automata, Academic Press, New York Dewdney A.K. (August 1989), A Cellular Universe of Debris, Droplets, Defects and Demons, Scientific American, 261:2, 102-105 Dewdney A.K. (January 1990), The Cellular Automata Programs That Create Wireworld, Rugworld and Other Diversions, Scientific American, 262:1, 146-149 Dirac P.M. (1963), The Evolution of the Physicists, Scientific American, May 1963, p.45 Doolen G. (Ed.) (1991), Lattice Gas Methods for PDE's, Physica D 47 Gardner M. (1983), Wheels, Life and Other Mathematical Amusements, W.H. Freeman, New York Gardner M. (April 1970), The Fantastic Combinations of John Conway's New Solitaire Game of "Life", Scientific American, 223:4, 120-123 Gaylord R.J., Nishidate K., Modeling Nature: Cellular Automata Simulations with Mathematica, TELOS/Springer-Verlag publishers. Gerhardt M., Schuster H. (1989), A Cellular Automaton Describing the Formation of Spatially Ordered Structures in Chemical Systems, Physica D 36 Gerhardt M., Schuster H. (1995), Das digitale Universum - Zelluläre Automaten als Modelle der Natur, Vieweg, Braunschweig/Wiesbaden Grassberger P. (1984), Chaos and Diffusion in Deterministic Cellular Automata, Physica 10D, 52-58 Hayes B., Zelluläre Automaten, Computer Kurzweil, Spektrum der Wissenschaft, Heidelberg Kauffman S.A. (1984), Emergent Properties in Random Complex Automata, Physica 10D, 145-156 Kuhn T. (1970), The Structure of Scientific Revolutions, University of Chicago Langton C.G. (1984), Self-Reproduction in Cellular Automata, Physica 10D, 135-144 Lim H.A. (1988), Lattice Gas Automata of Fluid Dynamics for Unsteady Flow, Complex Systems, 2, 45-68 Lorenz K. (1993), Die Rückseite des Spiegels - Versuch einer Naturgeschichte menschlichen Erkennens, dtv 12.Aufl. München Mach E. (1905), Erkenntnis und Irrtum, Barth, Leipzig Mach E. (1910), Die Leitgedanken meiner Naturwissenschaftlichen Erkenntnislehre und ihre Aufnahme durch die Zeitgenossen. Physik. Zeit. 11. S 599-606 Margolus Norman (1984), Physics-Like Models of Computation, Physica 10D, 81-95 McCauley J.L. (1993), Chaos, dynamics, and fractals : an algorithmic approach to deterministic chaos, Cambridge [England] : Cambridge University Press Neumann von, John (1966), Theory of Self-Reproducing Automata, University of Illionois Press, Champain, IL Neuser W. (Hrsg.) (1996), Quantenphilosophie, Heidelberg, Spektrum, Akad.Verl.m Omohundro S. (1984), Modelling Cellular Automata with Partial Differential Equations, Physica 10D, 128-134 Ott E., Sauer T., Yorke J.A. (1994), Coping with chaos : analysis of chaotic data and the exploitation of chaotic systems, New York : J. Wiley Popper K.R. (1934), Die Logik der Forschung, J.C.B Mohr, Tübingen Riedl R. (1985), Evolution und Erkenntnis, Piper, München Schiff, Joel (2007), Cellular Automata: A Discrete View of the World (Wiley Series in Discrete Mathematics and Optimization), Wiley Toffoli T., Margolus N. (1987), Cellular Automata Machines: A New Environment for Modeling, The MIT Press, Cambridge, Massachussetts Toffoli T. (1984), Cellular Automata as an Alternative to (Rather than an Approximation of) Differential Equations in Modelling Physics, Physica 10D, 117-127 Vichiniac G.Y. (1984), Simulating Physics with Cellular Automata, Physica 10D, 96-116 Willson S.J. (1984), Growth Rates and Fractional Dimensions in Cellular Automata, Physica 10D, 69-74 Winfree A.T. (1974), Rotating Chemical Reactions, Scientific American 230 Wolfram S. (1984), Universality and Complexity in Cellular Automata, Physica 10D, 1-35 Xiao-Guang Wu, Kapral R. (1994), Internal fluctuations, period doubling, and chemical chaos, Physical Review E, 50, 3560-3568 Physica 10D (1984), special issue: contains only CA-related articles 8.2 Internet Links Internet links are not provided any longer, as it is very hard to keep them up-to-date. Please refer to search machines like Google. top 9. And now to something completly different... I hope this tutorial was interesting for you! Please check out also other content from my website: Read the Genetic Algorithm tutorial Check out quotations from several scientific sources Publictions in various journals and conferences Probably you are also interested in my university courses or in doing a diploma thesis or read finished ones.. top last changed at 2008-01-18(c) by Alexander SchattenContact/Feedback _uacct = "UA-948081-1"; urchinTracker(); |
|
