Cellular Automata
Cellular Automata
Dateline: 08/31/99
The first and fundamental difference between machines and organisms is the fact that machines are constructed, whereas organisms grow by themselves. In the early fifties, one of the best mathematicians of this century, John Von Neumann, was trying to develop what he called a self-replicating automaton. The legend says that never actually intended for the machine to be built. His goal was to invent a set of rules by which a computer could be programmed to produce an exact replica of itself. After trying out a number of unsuccessful approaches, Von Neumann teamed with a fellow mathematician, Stanislaw Ulam, and produced a general, simple and elegant solution. It uses a rectangular array of cells, in which each cell can exist in one of a finite number of states. Initially, all cells are in the same state, say 0. Some cells are randomly placed in nonzero states to start the automaton. As time in this model progresses discretely, each tick of the clock brings a chance for each cell to change its state. The rule governing these changes depends only upon the states of the cell's immediate neighbors and possibly upon the state of the cell itself. Now just sit back and watch how your model progresses, and voila, you've just constructed your first cellular automaton. Actually, Von Neumann's complete solution required hundreds of thousands of cells, each of which could exist in one of 29 different states. It was published posthumously in 1966 as the Theory of Self-Reproducing Automata.
Our understanding of living organisms will have to be more process-oriented, and Cellular Automata provide an excellent foundation for this type of research.
|
Speaking formally, a cellular automata (CA) has three fundamental characteristics: parallelism (all states are updated simultaneously), locality (new state of the particular call is based exclusively on its old state and the state of the neighboring cells) and homogeneity (use of the same set of rules for the whole automaton). The beauty of the whole concept arises from the fact that complex patterns and behaviors can result from simple rules and algorithms. This emergent order, as we'll see later, is one of the most important concepts in ALife and Evolutionary Computing in general.
The most popular cellular automata is "Game of Life", developed by mathematician John Conway of the University of Cambridge, England, in the late sixties. It was first used as an elementary imitation of a colony of living cells. When Conway created the rules for his simulation, he didn't have access to a computer. To experiment with the new rules, he used stones on a Go board, and he updated the patterns one stone at a time. At the end, the system was built on a two-dimensional grid, on which all cells live, die, and are born according to a simple set of rules:
- birth: if exactly three "live" cells are adjacent to an empty cell, the empty cell comes to life
- overpopulation: when a cell has four or more live neighbors, it dies from overcrowding
- underpopulation: any cell with one or no neighboring cells dies from loneliness.
The patterns that can arise from certain starting positions are very complex and fascinating. The same holds for the amazing concept of transmitting information via only localized interaction. Another interesting finding is that such a system can perform arithmetic, and thus it is possible to build a computer from a sufficiently rich pattern of cells. This gives another name to Cellular Automata: they are also known as Universal Computers, because of their ability to complete any task given an appropriate initial pattern.
The Game of Life is a CA in two dimensions, however we can generalize to fewer or more dimensions. There is a great number of possible rules for such systems. The scope of cell's neighborhood can be local (touching), close (neighbour's neighbors) or global (anywhere in the system), while interactions can range from few neighbors to all of them. Some schemes will even allow the cells to grow or die out, mimicking living systems to even greater extent. Other allow for each cell to have a different set of rules - they are called non-uniform CAs, and are the fundamental building brick for Cellular Programming and other Evolutionary Computation techniques.
According to Stephen Wolfram, the various types of CA fall into 4 categories:
Class 1: point attractors, where the system falls into a fixed state after a short time.
Class 2: limit cycles, in which the system develops periodic repeating behaviours.
Class 3: chaotic, when the system becomes aperiodic, continuously changing in unpredictable ways.
Class 4: structured, where the system develops highly patterned but unstable behaviours. This is where the "Game of Life" belongs.
As it turns out, the structure of the rules employed directly affects the behaviour of the particular CA. For example, cell state should change between 25% and 50% of the time for Class 4. Less than this generally leads to static behaviour (Classes 1 & 2), more to chaotic behaviour (Class 3).
CA are used for modelling fluid flows, ecological systems and urban development, in cryptography, image processing, etc. Besides these practical applications, the importance of the whole concept may be much larger. The increasing prominence of computers has led to a new way of looking at things, especially living organisms. The problem lies in the fact that many people still have the naive idea (dating from old days of AI) that you can formalize the mind and program it like a digital computer. If we draw some experience from subatomic physics, we'll see that the notion of an independent physical entity has become problematic and outdated, and so has the notion of an independent organism in biology. Living organisms are open systems, which keep themselves alive and functioning through constant interactions with their environment, which also consists (at least partially) of other organisms. Our understanding of living organisms will have to be more process-oriented, and CA provide an excellent foundation for this type of research.
The broad coverage of this topic would require dozens of lengthy articles. Fortunately, the best way to learn about it is to interact with some of CA simulators, either Java applets or standalone programs. You'll find an extensive list of such resources below.
Site(s) of interest:
- FAQ
Answers to general questions, software and hardware, Game of Life, applications, etc.
- Primordial Soup Kitchen
David Griffeath is math professor at the University of Wisconsin, Madison. More importantly (at least for us), he is a creator of this excellent site dedicated to CA and related topics. You should really try his cooking!
- CALResCo
Excellent resource for Complexity and ALife research, including Cellular Automata resources.
- Tutorial
Short tutorial including a list of related links.
- Cellular Automata
"Life might look like a mathematical game, but it lives up to its ambitious name. Cellular automata could reveal a lot about how the universe works and maybe even about how life began." Excellent page with applets, explanations and links.
- CAM8
Parallel, uniform, scalable architecture for cellular automata experimentation.
- Cellular Computing
Wealth of information on cellular computing and parallel cellular machines from Moshe Sipper.
- XToys
A set of cellular automata simulators for Xwindows.
- Mirek's Cellebration
The official version 2 of Cellebration, new 32-bit CA program for Windows, and probably the best general-purpose engine on any platform. An older, but still very popular simulator known as WinCA can be downloaded right here.
- CAM Brain Project
Brain Builder Group at ATR, a research lab in Kyoto, Japan, is building an artificial brain using evolved cellular automata based neural circuit modules.
- EvCA
Using genetic algorithms to evolve cellular automata to perform computational tasks requiring globally-coordinated information processing.