Cellular automata

Type of physical science: Computation

Field of study: Artificial intelligence

Cellular automata are discrete self-organizing systems that mirror biological processes. Their primary application is the construction of simple models to explain complex phenomena in nature, such as weather patterns and immune system reactions.

Overview

A cellular automaton is a discrete self-organizing system whose behavior at any time is dependent upon previous states of the system. Such a system behaves in a preprogrammed fashion, growing from simplicity to complexity by cause-and-effect relationships with its environment. It usually produces a pattern that is repeatable from microscale to macroscale. The development of this pattern remains steady given unchanged conditions in the environment and unchanged programming rules. There are many examples of cellular automata in the universe, in living organisms and in biochemical processes. Scientists use cellular automata as simple, predictable models for describing complex processes, both physical and biological.

The Hungarian-American mathematician John von Neumann first coined the term "cellular automaton" in 1948. He defined it as any system that organized itself and developed in particular patterns based upon predictable rules. He envisioned a machine, now called a von Neumann machine, that would be capable of replicating itself from available materials. This hypothetical machine has been popularized in numerous science-fiction books and films.

Von Neumann was interested in understanding biological processes and reproducing them on computer. Being a pioneer in the development of computer technology, he saw very early, even before many biologists, that living processes were orderly, followed predictable patterns, and behaved in a programmable format that could be altered. His concept of a von Neumann machine already existed: It was life. Life is a cellular automaton that self-organizes and replicates in predictable patterns. Von Neumann's goal was to reproduce biological processes on computer, to generate a living process artificially, or at least to model it. His primary focus was the human nervous system: he wished to produce a simple computer model--a cellular automaton--that could mimic the development and functions of an animal nervous system.

John von Neumann died in 1957. His brilliant work would not be completed until 1970 by several followers, among them Stanislaw M. Ulam, Arthur Burks, and John H. Conway. In 1970, Conway and his colleagues at the University of Cambridge developed the Game of Life, a statistical model designed to mirror simple biological processes, most specifically the birth, evolution, and death of a population. The game, which was popularized in SCIENTIFIC AMERICAN, comes in several forms and has stimulated considerable mathematical analysis.

The one-dimensional life game is performed on a two-dimensional grid. Any block on the grid has eight neighbors. If a given block is occupied by an individual at time t, then it must have two or three neighbors in order to survive to time t + 1. Yet, if the individual is located in an underpopulated area (either zero or one neighbors) or in an overpopulated area (four or more neighbors), then it does not survive to time t + 1; at time t + 1, its grid block will be unoccupied. Such are the constraints for survival and death. For birth, an unoccupied site at time t becomes occupied with a new individual at time t + 1 if the unoccupied site at time t had three occupied neighboring sites. One possible life game scenario would proceed as follows:

If one continued the model life game scenario above, the population would become extinct at generation t + 4 because of scattering. Such a model is very useful for simulating the real-life population dynamics of animal groups, such as deer and birds. Many different results can be obtained from the life game, including infinite growth, based upon starting conditions.

The game can be performed with zeros and ones instead of a grid. The game can also be performed either with pencil and paper or with a computer.

The population sample in the life game above generates a series of patterns. When these patterns are somewhat similar, they are termed "self-affinity." When they are exact duplicates, they are termed "self-similar." A major feature of cellular automata is their self-similar patterns. As the cellular automaton develops, the same pattern is reiterated over and over again in different parts of the structure and from microscales to macroscales. This reiteration of specific patterns is termed a "fractal," and many cellular automata can be represented as fractals.

Benoit B. Mandelbrot of the International Business Machines Corporation (IBM) Thomas J. Watson Research Center in New York and of the Mathematics Department at Yale University in New Haven, Connecticut, first coined the term "fractal." A fractal is a pattern that is reiterated over and over within a structure from microscale to macroscale, and vice versa.

Cellular automata and their corresponding fractal structures are common in living systems. For example, the branches of a tree, the patterns of arteries, veins, and capillaries in an animal circulatory system, and the organization of neurons in the human brain are all fractal cellular automata. Whether one looks at these structures at low or high magnification, the same patterns are repeated.

An example of a fractal cellular automaton is the Sierpinski carpet shown below. One begins with a square within a square at time t, then eight smaller squares around the innermost square at time t + 1, then eight smaller squares around each of those squares at time t + 2, and so on to infinity. The model below shows only the first three stages:

The Sierpinski carpet has a fractal dimension D = ln 8/ln 3 = 1.89. Eight is the number of squares added around each starting square per time interval. Three is the number of squares at time t that can fill the large field square from side to side. The symbol ln is the natural logarithm of these numbers. A fractal dimension D, which is greater than 1.00, is a characteristic feature of all fractal cellular automata.

The Sierpinski carpet is only one of numerous fractal cellular automata constructed by Mandelbrot and other fractal geometers and mathematicians interested in the topology or geometry of nature. Mandelbrot became a driving force in the field of fractal geometry. His computer-generated fractal simulations became so sophisticated that they could generate almost lifelike images of common objects found in nature, such as trees, ferns, people, flowers, and mountain valleys.

A major criticism of fractal geometry is that it offers no practical applications other than generating pretty pictures, although impressive real-life images. Stephen Wolfram of the Institute for Advanced Studies at Princeton University in New Jersey produced models of cellular automata designed to simulate highly complex physical and biological processes. His work legitimized cellular automata and fractal geometry, showing their potential as highly productive research activities. Wolfram, a theoretical physicist, applied cellular automata to the construction of computer models involving up to 100,000 different elements. He used cellular automata to model thermodynamics, hydrodynamics, and cosmology.

Many processes and structures in the physical and biological worlds exhibit cellular automata-like behavior. Many such processes are regular or cyclical, such as the Great Red Spot of Jupiter and the Great Dark Spot of Neptune, gigantic hurricanes that are hundreds of years old.

The structure of DNA (deoxyribonucleic acid), which is the information molecule of life, and predator/prey interactions also are cyclical cellular automata. Natural systems often are dynamic and constantly changing, although they repeat in predictable cycles. If these cycles are disturbed, however, their orderly cellular automata-like behavior becomes disordered, or chaotic.

Ordered cellular automata can become disordered, or chaotic, when natural environmental conditions change. For example, old field ecological succession in eastern North America begins with an abandoned field becoming overgrown with grass, then shrubs, then pine and cedar trees, and finally with a climax community of organisms dominated by hardwood trees such as oaks and hickories. The climax community is stable. Nevertheless, any catastrophe (for example, fire or disease) disrupts all plant and animal life in the community. The affected areas must rezero and restart at the first stage of this evolutionary process.

At the Massachusetts Institute of Technology, the meteorologist Edward N. Lorenz made significant contributions toward the study of chaotic cellular automata with his computer simulations of weather processes. His efforts were aimed at weather prediction. Nevertheless, he discovered that the slightest fluctuations in his input data, even from rounding-off numbers or from other computer-related adjustments, drastically altered what should have been predictable weather patterns. He discovered the "Butterfly effect": A butterfly flapping its wings in Japan, for example, potentially can affect major weather patterns halfway around the earth. In other words, the slightest disturbance in any process can drastically alter that process, thereby making it chaotic. Little effects add up to big effects. Short-term weather prediction--that is, for the next few days--is possible, but long-term weather prediction is impossible.

Ideally, cellular automata should be continuous and unchanging over time, which is true for most systems within finite time periods. Nevertheless, cellular automata eventually lose information from outside influences, thereby becoming disordered. Chaotic cellular automata behavior is inevitable based upon the second law of thermodynamics, which maintains that the entropy (disorder) of the entire universe is increasing. No orderly system can remain so forever.

Living organisms grow and develop high complexity and order; however, living organisms also age and die. Certain diseases and ailments exhibit chaotic behavior. The human heart beats rhythmically more than two billion times in an average human lifetime, but it becomes disordered during a heart attack. Scientists from many fields are interested in cellular automata as models of basic processes that on the surface seem simple but that actually are very complex.

Applications

Cellular automata represents a means of mathematical modeling for dynamical systems in nature. Whereas Mandelbrot and others have made tremendous advances in cellular automaton and fractal research with computer-generated images that are almost lifelike, the full impact of cellular automata as practical and productive research tools has not yet been fully achieved. A number of researchers, including Mandelbrot, Wolfram, Michael Barnsley of the Georgia Institute of Technology, and Max Dresden and Andrew Ilachinski of the State University of New York at Stony Brook, among many others, are driving this science to describe phenomena in physics, chemistry, biology, geology, and meteorology.

In physics and chemistry, cellular automata are very useful in modeling fluid flow, hydrodynamics, thermodynamics, and kinetic rates of reaction and in studying the distribution of galaxies through space and the motion of planets around the sun. The concept of universality maintains that the same basic patterns will repeat themselves throughout the universe. A common pattern is the spiral, which is found in such structures as DNA, certain viruses and cellular organisms, tornados, hurricanes, ocean currents, planetary systems, and galaxies themselves. A major potential benefit from cellular automaton research is the discovery of common themes and forms that explain the nature and form of practically everything in the universe. The science of cellular automata seeks to unravel a geometry of nature.

In biology, cellular automaton research began to be productive in the 1960's. This work was stimulated by von Neumann's attempts at computer-simulating an animal nervous system, the first attempts to produce an artificial intelligence. Burks completed von Neumann's simulation, although biologists still have an incomplete understanding of nervous systems as complicated as the mammalian brain. Several prominent biologists, including Nobel laureate Francis Crick, have delved into computer models of the human brain and other mammalian brains. Cellular automaton research has contributed to models of nerve impulse transmission, muscle contraction, the electrical activity of the heart, and the chaotic behavior of disease.

In ecology and population biology, mathematical models similar to the life game have been used to study the growth of animal, plant, and microorganism populations. Very detailed models of predator/prey and host/parasite interactions have been generated. Mathematical models have described the evolution of populations over time, including predicted growth patterns, and the spread of disease through populations of organisms. Cellular automaton models have contributed to an improved understanding of physical, chemical, and biological phenomena and have assisted the growth of modern technology and medicine.

Mathematical models involving cellular automata require the use of personal computers (for example, IBM PC, Apple IIe), appropriately programmed fractal graphics software, and either an EGA or a VGA graphics monitor plus an adaptor. Several inexpensive fractal disks (both soft and hard) are available from computer dealers. Many fractal programs are written in C language; a few are written in BASIC. An ink-jet or paint-jet printer is a very useful accessory.

An alternative approach to producing one's own cellular automata and fractals is to use a video camera and television monitor. With the television monitor set on an unoccupied station, the video camera is aimed at the monitor so that the monitor is centered within the camera's field of view. A connecting cable is used to link the video output of the camera to the video input of the monitor; one must ensure that the correct auxiliary video input dial is selected on the monitor.

Once in operation, the television monitor will display itself projected to infinity. The camera/monitor system is looped so that the image of the television monitor and other nearby objects, including the reflection of room lights, is reiterated. By tilting the camera at any angle from 0 to 180 degrees and by varying the camera focus, a variety of fractal patterns can be generated, including spirals, stars, flowers, and the like. The camera/monitor system can be linked with a videocassette recorder for taping.

Context

Cellular automata and fractals serve as mathematical and topological models for describing physical and biological processes. Together, they unravel basic patterns that are reiterated in nature. So far, their primary use has been the computer generation of process simulations and lifelike images. Their potential uses include the discovery of a geometry of nature, where certain basic patterns emerge throughout the universe.

Von Neumann's early experiments with automata were aimed at machine intelligence, or artificial intelligence. He possessed the foresight to see the ordered, programmable features of living organisms. In fact, he made these observations before biologists deciphered the genetic code of DNA. Computers are programmable machines; likewise, living organisms are programmable machines.

Theoretically, the production of a thinking, self-replicating machine should be possible in the future. Von Neumann was one of the first scientists to envision this possibility. His experiments to simulate an animal nervous system on a computer were steps in the right direction. Nevertheless, the mammalian brain is so incredibly complicated that even the most powerful supercomputers cannot perform an adequate reproduction or simulation.

Still, the programmability (or predictability) of natural processes, including life, make cellular automaton simulations on a computer a valuable tool for studying physical and biological processes. Consequently, physiologists, epidemiologists and medical doctors can study the spread of disease, immune system reactions, and neuromuscular activities. Ecologists can study population movements and distributions, interactions between species, and the evolution of life-forms. Physicists can study orderly and disorderly behavior in periodic processes. The increase in entropy dictated by the second law of thermodynamics means that all cellular automata, including humans, will occasionally be subject to chaotic, or disorderly, behavior.

The lifelike fractal computer images produced from cellular automaton research have spawned the use of computers in art and special effects for motion pictures. The reemergence of certain patterns, such as spirals, throughout nature indicates that there are specific forms that govern the stability of the universe. It is this knowledge of form and structure that cellular automaton researchers seek to discover. The benefits of such research could be seen in improved technology and medicine, as well as in the development of computer intelligence.

Principal terms

CHAOS: the tendency for ordered natural processes to become disordered, and vice versa, often because of the influence of minute external factors

CONTINUOUS: a term describing a self-organizing system that is stable in information content and symmetric in growth pattern

DISCRETE: a term describing a self-organizing system in which information is lost during pattern formation because of entropy (disorder)

DYNAMICAL SYSTEM: a system that is constantly changing either in a predictable, cyclical pattern or in a disorganized, chaotic fashion because of external cues

FRACTAL: a pattern that is reiterated (repeated) over and over again within the three-dimensional structure of a system, from macroscale to microscale

LIFE GAME: a statistical model used to illustrate self-organization, where a system evolves a complex pattern by following predictable rules

SELF-AFFINITY: a semifractal self-organizing system in which complex patterns are repeated on both small and large scales

SELF-SIMILAR: a true fractal self-organizing system in which the same pattern of structure is reiterated from microscale to macroscale

STRANGE ATTRACTOR: a phenomenon in which chaotic systems reorganize themselves around a single point or points (for example, a hurricane spiraling around its vortex nucleus, or eye)

UNIVERSALITY: the organization of structures throughout the universe from small to large based upon certain reiterated fractal patterns

Bibliography

Devaney, Robert L., and Linda Keen, eds. CHAOS AND FRACTALS: THE MATHEMATICS BEHIND THE COMPUTER GRAPHICS. Proceedings of Symposia in Applied Mathematics, vol. 39. Providence, R.I.: American Mathematical Society, 1989. This short book is a collection of papers presented at an American Mathematical Society course on fractal geometry. Somewhat detailed with mathematical equations, but a solid background is provided for fractal computer graphics.

Feder, Jens. FRACTALS. New York: Plenum Press, 1988. This excellent book is a clear, comprehensive discussion of fractals and their uses. Numerous examples are presented, along with simple mathematical explanations. Feder, a Norwegian physicist, has assembled a book that is a refreshing alternative to other mathematically rigorous fractal books.

Glassner, Andrew S., ed. GRAPHICS GEMS. Boston, Mass.: Academic Press, 1990. This reference work is a collection of "how-to" hints for the graphics computer programmer. The book is almost exclusively oriented toward computer applications, especially toward the use of graphics in mathematical modeling.

Gleick, James. CHAOS: MAKING A NEW SCIENCE. New York: Viking Press, 1987. Gleick's popular book is an excellent survey of cellular automata, fractal geometry, and chaos for a general audience. He describes the development of research in these fields and cites numerous important experiments.

Moore, Edward F. "Mathematics in the Biological Sciences." SCIENTIFIC AMERICAN 211 (March, 1964): 149-164. This review article is a discussion of mathematical modeling techniques that are used in the biological sciences. Cellular automata are discussed with their applications to biology. Von Neumann's work is also described.

Peitgen, Heinz-Otto, and Peter H. Richter. THE BEAUTY OF FRACTALS. New York: Springer-Verlag, 1986. This beautifully illustrated book is an introduction to fractal geometry and some of the mathematics behind fractals. Includes a guest paper by Mandelbrot and applications of fractals to biology and physics.

Pickover, Clifford A. COMPUTERS, PATTERN, CHAOS AND BEAUTY: GRAPHICS FROM AN UNSEEN WORLD. New York: St. Martin's Press, 1990. This outstanding book is a step-by-step introduction to fractal geometry and computer graphics. It is clearly written, beautifully illustrated, and somewhat philosophical in scope.

Numerous fractal-generating algorithms are presented. Silbar, Margaret L. "Cellular Automata." ANALOG SCIENCE FICTION/SCIENCE FACT 107 (September, 1987): 68-80. An excellent introduction to cellular automata for the layperson. Silbar summarizes the history of automaton research, including the work of John von Neumann, John H. Conway, and Stephen Wolfram. The Game of Life is described in simple terms.

Stevens, Roger T. FRACTAL PROGRAMMING IN C. Redwood City, Calif.: M&T Books, 1989. This outstanding "how-to" book is a description of fractal structures and how the reader can begin to write personal fractal programs. A knowledge of C language programming is expected, along with a knowledge of appropriate computer graphics equipment.

One possible life game scenario

Sierpinski carpet

Nonlinear Maps and Chaos