Cellular Automata
With the advent of computers and their use in simulation has come the need to model complex interactions. One of the ways of doing this is to consider all interacting entities in a system as processors--each entity carries out its own computations, and passes on state information to its immediate neighbors, who use it as input for their own computations. Each entity may be running its own program, and what we would be interested in is the global behavior of the system over time.
With this perspective in mind, a "cellular automaton" is an array (in two or more dimensions) of identical entities called "cells," which interact with one another. Cells are distinguished by the following three important properties:
- State--the current state of a cell is a variable (or more generally, an n-tuple) that describes it.
- Neighborhood--the neighborhood of a cell is a specification of the non-empty set of cells which interact or communicate with it. Generally, the neighborhood is taken to be the set of cells immediately contiguous with a given cell in a physical or topological sense, but more complex definitions are possible.
- Program--the program of a cell is the set of rules for state changes that completely specifies its behavior. The program of a cell usually defines a finite-state machine.
The advantage of the cellular structure is that it allows a simple yet well-defined interactive system capable of exhibiting complicated behavior. Without the cellular structure, there would be infinitely many possible connections between components.
Although cellular automata may appear quite simple as defined, they can exhibit very complex and "life-like" behavior. In many instances the behavior of a cellular automaton may not be theoretically obvious, and may have to be determined by simulation.
Some properties that are often seen in cellular automata include:
- Self-organization: after a certain number of state changes, there start to emerge macro patterns. Even if the individual cells are started in arbitrary states or are perturbed in between, the larger patterns among them will often surface after a fixed number of interactions.
- Life-like behavior: empirical observations of cellular automata have revealed that cellular automata can display behaviors usually associated with (communities of) life-forms. These include growth, dying out after a while, becoming stable or going into cycles with fixed periods, "fighting" between patterns, and so on.
In the 1940s, the mathematician Stanislaw M. Ulam liked to invent pattern games for the computer at Los Alamos. Given certain fixed rules, the computer would print out ever-changing patterns. Many patterns grew almost as if they were alive. A simple square might evolve into a delicate, coral-like growth. Two patterns would "fight" over territory, sometimes leading to mutual annihilation. He developed 3-D games too, constructing thickets of coloured cubes as prescribed by computer. He called the patterns "recursively defined geometric objects." Ulam's games were cellular games. Each pattern was composed of square (or triangular or hexagonal) cells. In effect, the games were played on limitless chessboards. All growth and change of patterns took place in discrete jumps. From moment to moment, the fate of a given cell depended only on the states of its neighbouring cells.
Ulam suggested that John von Neumann "construct" an abstract universe for his analysis of machine reproduction. It would be an imaginary world with self-consistent rules, as in Ulam's computer games. It would be a world complex enough to embrace all the essentials of machine operation, but otherwise as simple as possible. Von Neumann adopted an infinite chessboard as his universe. Each square cell could be in any of a number of states corresponding roughly to machine components. A "machine" was a pattern of such cells. The rules governing the world would be kept simple. A proof of machine reproduction would be easier to devise in such an imaginary world, as all the nonessential points of engineering would be stripped away.
The first cellular automaton was conceived by John von Neumann in the late 1940s. von Neumann's work on self-reproducing automata was completed and described by Arthur Burks. In the same environment, (the Logic of Computers Group of the University of Michigan), John Holland started applying cellular automata to problems of adaptation and optimisation, and a general-purpose cellular automata simulator program was developed.
The "Game of Life," a 1961 invention of the Cambridge mathematician John Conway, is a very well-known but simple cellular automaton that exhibits the behaviors of many living organisms.
This is the complete article, containing 719 words
(approx. 2 pages at 300 words per page).
