|||
The answer to these questions is unfortunately far from being simple. cellular automata are abstract constructions with quite complex properties not very accessible.
As a sideline, John von Neumann, relying on A. Turing's works, interested himself on the theory of self-reproductive automata and worked on the conception of a self-reproductive machine, the "kinematon". Such a machine was supposed to be able to reproduce any machine described in its programs, including a copy of itself. The most famous of his machines is the monolith of the series "2001 Space Odyssey". To change Jupiter into a star, a first monolith self-reproduces, as well as its descendants, the population so increases exponentially to quickly reach the size necessary to realize such a gigantic task.
Ulam suggested von Neumann to use what he named "cellular spaces" to build his self-reproductive machine. He could so liberate himself from real physical constraints to work in an extremely simplified universe that was nevertheless able to generate a high complexity. The use of this formal universe led him to notice : "By axiomatizing [self-reproductive automata with cellular automata], one has thrown half of the problem out the window, and it may be the more important half. One has resigned oneself not to explain how these parts are made up of real things, specifically, how these parts are made up of actual elementary particles, or even of higher chemical molecules. [...] The question we hope to answer now [...] is : what are the basic principles which underlie the organization of these elementary parts in living organisms ? My discussion will be limited to that point of vue.". On this base, he designed an about 200.000 29 states cells , containing a universal replicator, a description of itself and a Turing machine for supervision.
Cellular automata left laboratories in 1970 with the now famous Game of Life of John Horton Conway.
Originally, the Game of Life is presented as a mathematical game. Its description will allow us to materialize and better understand what cellular automata are.
Like Ulam's cellular spaces, the game of life is based a grid constituted of cells, for example :
Example of a starting pattern
The universe is here limited to a rectangle of 5 by 3. To make the explanation easier, we numbered the cells from 0 to 4 horizontally and from 0 to 2 vertically. Light cells are active ones.
In the game of life, any adjoining cell is considered as neighbour, including diagonals.
Determination of neighbourhood
The graphic above shows the neighbourhood of cell 12. In this case, two cells are active out of the 8 neighbours.
The rules of the game of life are quite simple :
We can interpret these rules by considering that a birth supposes a certain gathering of population, (3 in this case), that the cells cannot survive to a too wide isolation (less than two neighbours) and that a too strong concentration will kill them (more than 3 neighbours).
Cellular automata work in a discrete manner. That is to say time goes step by step. This means that in our case, for the g generation, each cell examines its environment and determines its future state. When all the cells have fulfil this computation, the transitions occur. We so simulate a simultaneous treatment.
Let us illustrate this mechanism starting from the previous pattern :
First generation
In the previous pattern, the number of active neighbours is noted for each cell :
For the next generation, only the cells 02,12 and 22 are then active.
Second generation
We show there the three fundamental properties of cellular automata :
The game of life is only one type of cellular automata among an infinity. It is indeed possible to play on the whole rules that govern the universe of cellular automata.
The most obvious parameter is the number of dimensions. Indeed, nothing obliges to consider two dimensions environments. The theoretical analysis of cellular automata was mainly made out of one dimension automata. By reducing the number of dimensions, one limits the combinatory explosion, hence the number of possible automata. If we consider the simple case of a three cells neighbourhood, i.e. the concerned cell and its right and left neighbours, in a one dimension and two states automaton, there are only 2 power 23=256 possible rules. With one dimension automata (i.e. one line) we use the second dimension to represent time. For each generation, a new line is added below the former one, we can so visualize the dynamic of this type of automata.
Example of a 1 dimension automaton (Pascal's triangle)
It is obviously possible to create three (or more) dimensions automata.
It is also possible to modify the determination of neighbourhood. If we consider two dimensions automata, the most common neighbourhoods are:
For example, Fredkin's automata, that uses a Moore neighbourhood is based on the parity of neighbourhood. It's a totalistic automaton, that is to say the state of the cells depends on the sum of the states of neighbouring cells. In this case there is reproduction only if there is an odd neighbourhood value. This automata has got the remarkable property to reproduce nine copies of any basic pattern. Fredkin's rule can easily be generalized to more than two dimensions.
Fredkin generation 0
![]() |
Fredkin generation 8
![]() |
It is also possible to modify the number of states. You needn't restrict yourself to both states life/death. Numerous famous automata use more than two states. One of the most famous is Brian's Brains presented by Brian Silverman in 1984. This three states automaton (life, ghost, death) generates a wide diversity of complex gliders within astonishing graphic patterns.
Brian's Brain
More complex rules can be imagined. It's possible, for example, to build stochastic automata whose transition rules integrate a probability function.
In a general way, it is possible to build any type of automata by playing on structural and functional rules. The first ones define the spatial structure of the automata network, that is its number of dimensions, the disposition of cells (squares, hexagons,… in a two dimensional automaton) and the type of neighbourhood determination. The second ones will determine the number of states and the transition rules. The choice of these two types of rules permits to build a universe adapted to the demanded aim.
D- Applications
Cellular automata applications are diverse and numerous. Fundamentally, cellular automata constitute completely known universes. Our Universe is submitted to the laws of physics. These laws are only partly known and appear to be highly complex. In a cellular automaton laws are simple and completely known. One can then test and analyse the global behaviour of a simplified universe, for example :
In a more daily field, cellular automata can be used as graphic generators. The several images below, generated with Capow, show some graphic effects.
![]() |
![]() |
![]() |
![]() |
But it is undoubtedly in the field of artificial life that cellular automata are most known.
E- Cellular Automata and Artificial Life
Since the beginning, von Neumann, considered cellular automata as tools to analyse the reproduction mechanisms of living being. Indeed, the properties of cellular automata permit to show and analyse some of the Living fundamental mechanisms.
The notion of emergence appeared with the general systems theory. In a general way it is said that "the whole is greater than the sum of the parts" or "The global behaviour is greater than sum of the behaviours of the individual parts". These expressions mean that the complex association of elements induces the apparition of new phenomena and mechanisms. "At each level (of the prebiotic, biotic and social evolution) new properties appear that cannot be explained by the sum of the own properties of each part that constitute the whole. There is a qualitative gap (…) the property of emergence is linked to complexity. The increase of the diversity of elements, the increase of the number of links between these elements, and the game of non linear interactions lead to hardly predictable behaviours.". The so-called "global" emergence then characterize the properties of a system that are new ones comparing to the properties of its isolate components, or organized in a different way. Life is undoubtedly part of these.
We examined previously the behaviour of a line of three vertical cells : at the first generation, we get three horizontal cells, at the second one, three vertical cells again. A line of three living cells then generates a cycle.
This pattern is a "blinker". A blinker is not made up of a group of given cells, it is a dynamic pattern that emerges within the space of cellular automata. The blinker seems to be independent ; it is a specific structure, particular inside its environment.
The rules of the game of life were determined so as to generate a wide diversity of unpredictable structures. The specialists listed a whole faun of patterns whose behaviours are astonishing. Complete libraries are available . One of the most famous is the glider. A given five cells pattern self-reproduces every four generations one cell away.
Even more than blinkers, gliders evoke emergence. It looks like a creeping animal, going all over the space on straight line. A glider is not a set of cells. At each generation, its cells are replaced. As the atoms that constitute you are not the ones you had at your birth, the components of the glider are constantly renewed. The application of the rules of the game of life induce the apparition of a dynamic, coherent and independent structure, with peculiar properties : this is the very nature of emergence. These properties can be used for specific aims. The glider is used to represent a signal, you will find an example in LogiCell.
Another remarkable pattern is also to be noted : the glider gun. It is a set of cells generating gliders. It made it possible to demonstrate that the population of the game of life could grow indefinitely. The classical p30 gun is used as a generator in LogiCell.
Glider gun
2- Self-Reproduction
How far can these emergences go ? Is the apparition of life possible inside the universes of Cellular Automata ?
The idea that it should be possible to create life inside a computer is based on the computing theory proposed by Turing. The ability of a universal Turing machine to emulate any other machine - i.e. fundamentally the fact that all sort of computers are equivalent - led von Neumann to consider how automata could self-reproduce. He more particularly wondered "what kind of logical organization of an automaton is sufficient to produce self-reproduction". It is the kinematon we mentioned above.
Some cellular automata can be used to construct universal Turing machines. The game of life is part of them. Considering the physical impossibility to realize the kinematon, we saw that von Neumann turned to the cellular automata to build his self reproductive automaton. This one was extremely complex since von Neumann considered a universal self replicator. In 1968, Edgar Codd proposed a simplified version of von Neumann's automata, that only used height states, but in this case again, Codd was considering construction universality. Things changed in the eighties with Christopher Langton. Langton considered that to study living systems inside a computer one only needs to consider necessary elements not sufficient one. He then gave up the idea of a universal replicator.
Langton's basic idea is that it is possible to conceive a cellular automaton supporting a structure whose components constitute the information necessary to its own reproduction. This structure is then both itself and representation of itself.
Langton's automaton uses height states and twenty-nine rules. The structure that reproduces itself is a loop constituted of a sheath within which circulates the information necessary to construct a new loop i.e. necessary to reproduction.
A Langton's loop
The cells in state 2 constitute the sheath, inner cells contain the information for reproduction. They are, in some way, the DNA of the loop. The sequences 7-0 and 4-0 propagate toward the tail. When they reach the extremity, the first ones extend the tail, the second ones construct a left-hand corner. The addition of a "sterilization" rule that blocks the evolution after a certain number of generations leads to the construction of some kind of coral.
Langton's loops
S. Levy, Artificial Life., Penguin, 1992.
Like von Neumann's automata, Langton's loops show that "one of the fundamental properties of living organisms, self reproduction, can be explained in terms of interactions of simple elements and that it can be studied in its logical principles independently of its physical realization".
Langton's loops cannot, in any way, be considered as "living", they are nothing but a limited self reproductive construction. According to Conway, if a large enough cellular space could be considered, life forms might appear within it, but it has been reckoned that it might only happen in a space of at least 10 power 1012 cells. As a reminder, the number of particles in the universe is estimated to less than 10100.
If apparition of life is envisaged, if some automata have computation universality properties, it is because these automata belong to a special category : cellular automata at the edge of chaos.
The number of possible cellular automata is potentially infinite. In this context, Wolfram wondered about the existence of cellular automata's general behaviour rules.
S. Wolfram studied one dimensional automata, with two states and a neighbourhood of 2. He only considered as "legal" the automata that firstly eliminate any cell without neighbour, and secondly, are symmetric. There are then only 32 "legal" automata that Wolfram systematically studied.
This study showed that, according to the author, numerous cellular automata, and maybe all of them, fall into four basic classes.
Class I- evolution leads to an homogeneous state.
Class I automata (rule 36)
Class II- Evolution leads to simple or periodic structures.
Class II automata (rule 40)
Class III- Evolution leads to chaotic states.
Class III automata (rule 18)
Class IV- Evolution leads to complex global structures.
Class IV automata (rule 20)
According to Wolfram, cellular automata belonging to class IV generate structures that are strongly reminiscent of the game of life. Yet it is known that this cellular automaton has the computational universality property. This means that : "Cellular Automata may be viewed as computers, in which data represented by initial configurations is processed by time evolution. Computational universality implies that suitable initial configurations can specify arbitrary algorithmic procedures". He then puts forward the hypothesis that class IV characterizes the automata having universal computation capability. In order to let this capability emerge, the cells must be able to communicate and to transmit information. In classes I and II automata cells are to strongly interdependent to allow a useful information processing. Class III automata are characterized by a too weak cells interdependence. Most of automata belong to classes I to III. They represent 30 over the 32 Wolfram's automata. cellular automata belonging to class IV are then only to be found in a minority of cases. The cellular automata that are at the limit between classes I and II on the one hand, and class III on the other hand, are the only ones to be capable to deal with information in a useful way, and therefore are the only "interesting" ones.
C. Langton was also interested in the existence of general classification rules of cellular automata but in a more general way. The difficulty lies into the number of possible automata. If we consider the only automata with 8 states and a neighbourhood of 5, there are 8 power 85, i.e. 832768 possible universes. Langton decided to classify the cellular automata depending on a general parameter . The
parameter is, in fact, the probability, within all possible neighbourhood configurations, that one given configuration should lead to an "active" cell, i.e. : 1 - (number of quiescent transitions/ total number of transitions) . Using this parameter to build transition rules, Langton managed to classify cellular automata. For a low value, cells quickly disappear. If the value is raised over about 0.2, cyclical or persisting structures appear. Over about 0.3, complex and unpredictable behaviours appear. Finally, over about 0.5, the multiplication of structures induces a chaotic behaviour. To a certain extent the
parameter indicates the temperature of the universe of the cellular automata.
The four following figures show examples of one dimension automata with eight states and a neighbourhood of 5.
=0.1
=0.25
=0.45
=0.8
We then find again Wolfram's classification, but in a more general framework. According to Langton, the automata belonging to class IV, those whose parameter is roughly to be found between 0.3 and 0.5, are those whose ability to process information is the most important. "(...) cellular automata capable of performing non trivial computation - including universal computation - are most likely to be found in the vicinity of "phase transitions" between order and chaos (...)".
J.C. Heudin uses a parameter () that, in two dimensions cellular automata, corresponds to the number of active neighbours necessary for a cell to remain unchanged. In the game of life, this parameter value is 2. He then redefines automata with four rules :
For=1, the probabilities of rules execution are R4>R3>R2>R1. For
= 2, we've got a complete inversion with R1>R2>R3>R4. Beyond 2, the order remains identical, but the rules R2, R3 and R4 are very seldom executed. Heudin then shows a fundamental change in the universe of cellular automata for
= 2. It is during this deep modification of the automata properties - this phase transition - that complexity appears : "To appear [complex] needs order and a pinch of chaos. This situation occurs only at the interface of both systems, at the border who leads to chaos.".
With the generalization of cellular automata behaviours, diversity of universal structures or the existence of life, tends to show that the laws of our Universe are precisely at the border between order and chaos. This is what Langton means in the expression : "life at the edge of chaos".
Conclusion
Cellular automata are abstract structures which make it possible to study virtual completely known universes. They help us to understand our Universe : "Thus complex physical and biological systems may lie in the same universality classes as the idealized mathematical models provided by cellular automata. Knowledge of cellular automaton behaviour may then yield rather general results on the behaviour of complex natural systems.".
The universal computation capability of some cellular automata, i.e. their capability to construct arbitrary complex structures, is not sufficient to prove the possibility of life apparition in these universes. Generalization of cellular automata behaviours to our Universe is not direct and its pertinence is hard to be proved. However, and as a conclusion, I let you think about the two following images.
Norman Packard's snowflake
S. Levy, Artificial Life, Penguin, 1992.
A real shell texture and its equivalent generated with a cellular automaton
Langton ed., Artificial Life an overview, MIT press, 1997.
![]() |
Adami Ch., Introduction to Artificial Life, Springer-Verlag, New-York, 1998.
Bertalanffy (von) L., Théorie générale des systèmes. Dunod, Paris, 1973.
Gutowitz H.A., Langton C.G., Methods for designing Cellular Automata with "Interesting" Behavior, 1994. Available at : http://www.santafe.edu/~hag/interesting/interesting.html.
Heudin JC, La Vie Artificielle, Hermès, Paris, 1994.
Heudin JC, L'évolution au bord du chaos, Hermès, Paris, 1998.
Langlois A., Phipps M., Automates cellulaires. Application à la simulation urbaine. Hermès, Paris, 1997.
Langton C.G., Studying Artificial Life with cellular automata, Physica D 22, 1986.
Langton C.G., Life at the edge of chaos, Artificial Life II, Addison-Wesley, 1991.
Langton C.G., Artificial Life in The philosophy of Artificial Life, Boden M. A. dir., Oxford readings in Philosophy, Oxford University Press, 1996.
Langton ed., Artificial Life. An overview, MIT press, 1997.
Levy S., Artificial Life. The quest for a new creation, Penguin, 1992.
Michell M., Hraber P.T., Crutchfield J., Revisiting the edge of chaos : Evolving Cellular Automata to perform Computations, Santa Fe Institute, Working Paper 93-03-014. Available at : http://www.santafe.edu/projects/evca/Papers/rev-edge.html
Morin E., La Méthode. I-La Nature de la Nature., Points, Seuil, Paris 1977.
Rosnay (de) J., Le macroscope. Vers une vision globale. Points, Seuil, Paris, 1975.
Rucker R., Walker J., Introduction to CelLab, http://www.fourmilab.ch/cellab/
Shatten A., Cellular Automata, Institute of General Chemistry Vienna University of Technology, Austria, 1997.
Toffoli T., Cellular automata as an alternative to Differential equations, in Modelling Physics, Physica 10D, 1984.
Von Neumann J. et Burks A. ed., Theory of Self-Reproduction Automata, University of Illinois Press, 1966.
Wolfram S., Universality and complexity in cellular automata, Physica D, 10:1-35, 1984. Available at : http://www.stephenwolfram.com/publications/articles/ca/84-universality/index.html
Jean-Philippe Rennard Ph.D. 12/2000.
http://www.rennard.org/alife
alife@rennard.org
Copyright : This text has been written for an educational purpose. It is free for any private use. If you want to use it for a non-commercial public purpose, please quote author and source. Commercial use is strictly forbidden unless written agreement.
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-1 16:20
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社