> online showcase > articles > Typical Uses of Cellular Automata

November 12, 2006

Typical Uses of Cellular Automata

1. Introduction

The previous paper, "How Cellular Automata Work," explained the theory of cellular automata and demonstrated the surprising complexity that can emerge from simple cellular automata systems. This paper explains how cellular automata can be put to work. First, it shows how cellular automata can be directly used to create multimedia content, to generate random numbers, or to build parallel computers. The main part of the paper then explains the chief use for cellular automata: modeling and studying natural systems, including life itself. The final section describes what is probably the best-known modeling application of cellular automata—the field of artificial life.

2. Generating Multimedia Content

One of the obvious fascinations of cellular automata are the complex and often beautiful patterns that they can generate. Some unusual examples can be seen at Rudy Rucker's [12] web page at http://www.cs.sjsu.edu/faculty/rucker/capow/examples.html. These cellular automata images come from the CAPOW (Cellular Automata & Electric Power) research project, which involves using continuous valued cellular automata to simulate the flow of electricity in a power grid. (As mentioned in the previous paper, cellular automata typically have an integral number of discrete states, but the states can also have a continuous range of possible values.)

According to Bottoni, Cammilli, and Faralli [9], cellular automata can be used by computer artists to generate visual or acoustic patterns for art or presentations. Bottoni et al. have created an application known as ExcapeMe (Extended Cellular Automata with Pluggable Multimedia Elements), which can be used by computer artists—as well as researchers and students studying cellular automata dynamics—to generate multimedia content by rendering cellular automata.

3. Cryptography and Random Number Generation

Cellular automata can serve as a source of random numbers that are used for encrypting messages, running simulations, and other purposes.

According to Sarkar 2000 [5], the configurations of a succession of cellular automata generations can be used as a random sequence. One-dimensional cellular automata are normally used for this purpose. Sarkar cites several specific applications that have been proposed for cellular automata generated random numbers, including private key cryptosystems, public key cryptosystems, and hash functions.

Wolfram [8] further reveals that the random number generator used for large integers in his Mathematica system is based upon the elementary cellular automata known as Rule 30, which was described in the previous paper (in "4. Other Types of Cellular Automata"). Wolfram states that this particular cellular automata type is used as a random number generator due to the fact that it has the interesting and useful property of being chaotic.

[11]

4. Implementing Parallel Computers

As discussed in the previous paper, some cellular automata have the property of universal computation, which means that in principle they can perform arbitrary computations. According to Wolfram [10], this property may be of more than theoretical interest, and might allow cellular automata to form an architectural model for building practical parallel-processing computers. The homogeneity of cellular automata (one of their basic properties that was discussed in the previous paper) would permit cellular automata to be readily implemented using integrated circuits. For example, it might be possible to fabricate on a single silicon chip one-dimensional, computationally-universal cellular automata with about a million cells and a time step of about a billionth of a second. The homogeneous, one-dimensional structure of the cellular automata would make finding defects relatively simple.

However, Wolfram [10] also points out that programming a cellular automata computer would require a radically new programming approach. He suggests that new programming technologies focus initially on problem domains for which cellular automata are inherently suitable, such as image processing.

5. Modeling and Simulation

Cellular automata, as implemented on computers, can be used to model a wide variety of complex biological and physical systems [7]. Although many natural systems—for example, turbulence in fluids or the formation of snowflakes—can be analyzed using traditional mathematical models such as differential equations, cellular automata often provide a simpler tool that preserves the essence of the process by which complex natural patterns emerge [11]. According to Wolfram [10], cellular automata are inherently more efficient at analyzing many natural systems than traditional computational methods because the mechanisms found in most natural systems are closer to those of cellular automata than to those of conventional computation.

The complex global patterns and behavior of an array of cellular automata emerge from the simple laws built into the individual cells. Thus, cellular automata are especially suitable for modeling any system that is composed of simple components, where the global behavior of the system is dependent upon the behavior and local interactions of the individual components. The following are some specific examples of biological and physical systems that have been effectively modeled using cellular automata:

[4]

6. Artificial Life

The field of artificial life attempts to model biological life—or even to create an artificial form of life—on a computer. One of the primary purposes of this pursuit is to determine how complex systems, such as life forms, can emerge in a universe where the increase of entropy is one of the most fundamental laws. [2] Artificial life is possibly the best-known application of cellular automata [4].

Cellular automata are an ideal tool for the computer modeling of life because they are analogous to life in fundamental ways. Namely, cellular automata are based on simple rules from which complex life-like behavior—including self-reproduction—can emerge given the right conditions (such as an appropriate lambda value), just as life appears to have emerged from relatively simple molecules with evolution pushing the molecular precursors of living systems toward the right conditions where complexity could emerge. [2]

6.1 Self-Reproduction of Cellular Automata

One of the most important properties that cellular automata must exhibit in order to model life is self-reproduction. John von Neumann and Stanislaw Ulam made the first attempts to create self-reproducing cellular automata. (They originally called cellular automata cellular spaces.) Von Neumann's self-reproducing cellular automata, however, were very complex. They required 29 states and could not be implemented on the computers of his day.

Christopher Langton, one of the chief founders of the field of artificial life, succeeded in creating much simpler cellular automata that displayed a self-reproducing loop structure and required only 8 states and 29 rules. He was able to create simpler self-reproducing cellular automata chiefly because he abandoned von Neumann's original requirement that self-reproducing cellular automata have the property of computational universality[1] [5].

The ability to create cellular automata that exhibit self-reproduction is theoretically interesting because it demonstrates that one of the essential properties of living systems—namely, self-reproduction—can result from the local interactions of simple elements and can be modeled and studied using abstract, logical models apart from biological life.

[4]

7. Conclusion

Cellular automata can be used directly to create visual or acoustic multimedia content, to generate random numbers for cryptography or other purposes, and possibly to build parallel computers. The chief use for cellular automata, however, is to model physical and biological systems. Cellular automata can often serve as simpler tools for modeling systems than traditional mathematical methods. They are ideal for modeling systems that—like cellular automata themselves—are composed of simple components that manifest complex behavior. A few examples are gas phenomena, urban development, immunological processes, and crystallization. The best known application of cellular automata, however, is modeling living systems. This application is the province of the emerging field of artificial life, which is concerned with modeling biological life or even creating an artificial form of life on a computer, in an attempt to fathom the mystery of the emergence of complex life forms in a universe of increasing entropy.

8. Reference List

[1] Dewdney, A.K. (1985). "Computer Recreations: Building Computers in One Dimension Sheds Light on Irreducibly Complicated Phenomena", Scientific American, Volume 252, May 1985.

[2] Eck, D.J. (2006). "Cellular Automata And the Edge of Chaos", Retrieved from http://math.hws.edu/xJava/CA/.

[3] Holland, J.H. (1998). Emergence: From Chaos to Order. New York: Basic Books, Perseus Books Group.

[4] Rennard, J.P. (2006). "Introduction to Cellular Automata", Retrieved from http://www.rennard.org/alife/english/acgb.html.

[5] Sarkar, P. (2000). "A Brief History of Cellular Automata", ACM Computing Surveys (CSUR), Volume 32, Issue 1.

[6] Weisstein, E.W. (2006). "Cellular Automaton", Retrieved from http://mathworld.wolfram.com/CellularAutomaton.html.

[7] Wolfram, S. (1982). "Cellular Automata as Simple Self-Organizing Systems", Caltech Preprint CALT-68-938 (submitted to Nature).

[8] Wolfram, S. (2002). A New Kind of Science. Champaign, IL: Wolfram Media, Inc.

[9] Bottoni, P., Cammilli, M., & Faralli, S. (2004)."Generating Multimedia Content with Cellular Automata", IEEE MultiMedia, Volume 11, Issue 4.

[10] Wolfram, S. (1983). "Cellular Automata", Los Alamos Science, Volume 9, Fall 1983, 2-21.

[11] Wolfram, S. (1984). "Computer Software in Science and Mathematics", Scientific American, Volume 251, September 1984.

[12] Rucker, R. (2006). "CAPOW (Cellular Automata & Electric Power)", Retrieved from http://www.cs.sjsu.edu/faculty/rucker/capow/index.html.


[1] Computational universality was discussed in the previous paper.


Valid HTML 4.01 Transitional