Cellular automaton

From Example Problems
Jump to navigation Jump to search

A cellular automaton (plural: cellular automata) is a discrete model studied in computability theory, mathematics, and theoretical biology. It consists of an infinite, regular grid of cells, each in one of a finite number of states. The grid can be in any finite number of dimensions. Time is also discrete, and the state of a cell at time t is a function of the state of a finite number of cells called the neighborhood at time t-1. These neighbors are a selection of cells relative to some specified, and do not change (Though the cell itself may be in its neighborhood, it is not usually considered a neighbor). Every cell has the same rule for updating, based on the values in this neighbourhood. Each time the rules are applied to the whole grid a new generation is produced.

One example of a cellular automaton (CA) would be an infinite sheet of graph paper, where each square is a cell, each cell has two possible states (black and white), and the neighbors of a cell are the 8 squares touching it. Then, there are 29 = 512 possible patterns for a cell and its neighbors. The rule for the cellular automaton could be given as a table. For each of the 512 possible patterns, the table would state whether the center cell will be black or white on the next time step. This is an example of a two dimensional cellular automaton. See Conway's Game of Life for the most popular CA of this form.

It is usually assumed that every cell in the universe starts in the same state, except for a finite number of cells in other states, often called a configuration. More generally, it is sometimes assumed that the universe starts out covered with a periodic pattern, and only a finite number of cells violate that pattern. The latter assumption is common in one-dimensional cellular automata.

Cellular automata are often simulated on a finite grid rather than an infinite one. In two dimensions, the universe would be a rectangle instead of an infinite plane. The edges are usually handled with a toroidal arrangement: when you go off the top, you come in at the corresponding position on the bottom, and when you go off the left you come in on the right (This essentially simulates an infinite periodic tiling). This can be visualized as taping the left and right edges together to form a tube, then taping the top and bottom edges of the tube together to form a torus (doughnut shape). Universes of other dimensions are handled similarly. This is done in order to solve boundary problems with neighborhoods. For example, with a 1-dimensional cellular automaton, like the examples below, the neighborhood of a cell xi t—where t is the time step (vertical), and i is the index (horizontal) in one generation—is xi-1t-1, xit-1, xi+1t-1, there are obviously going to be problems when a neighbourhood on a left border is going to reference the upper left cell as part of its neighborhood, which it cannot, since it is not in the cellular space!

History of cellular automata

Stanislaw Ulam, while working at the Los Alamos National Laboratory in the 1940s, studied the growth of crystals, using a simple lattice network as his model. At the same time, John von Neumann - Ulam's colleague at Los Alamos - was working on the problem of self-replicating systems. Von Neumann's initial design was founded upon the notion of one robot building another robot. This design is known as the kinematic model. As he developed this design, von Neumann came to realize the great difficulty of building a self-replicating robot, and of the great cost in providing the robot with a "sea of parts" from which to build its replicant. Ulam suggested that von Neumann develop his design around a mathematical abstraction, such as the one Ulam used to study crystal growth. Thus was born the first system of cellular automata. Like Ulam's lattice network, von Neumann's cellular automata are two-dimensional, with his self-replicator implemented algorithmically. The result was a universal copier and constructor (UCC) working within a CA with a small neighborhood (only those cells that touch are neighbors, and for von Neumann cellular automata, only orthogonal cells), and with 29 states per cell. Neumann proved mathematically that a particular pattern would make endless copies of itself within the given cellular universe. This design is known as the tessellation model.

In the 1970s a two-state, two dimensional cellular automaton named Game of Life became very widely known, particularly among the early computing community. Invented by John Conway, and popularized by Martin Gardner in a Scientific American article, its rules are as follows: If a black cell has 2 or 3 black neighbors, it stays black. If a white cell has 3 black neighbors, it becomes black. In all other cases, the cell becomes white. Despite the simplicity of the rule, an impressive diversity of behavior is achieved, fluctuating between apparent randomness and order. One of the most apparent features of the Game of Life is the frequent occurrence of gliders, which are arrangements of cells that essentially move themselves across the grid. It is possible to arrange the automaton so that the gliders interact to perform computations, and after much effort it has been shown that the Game of Life can emulate a universal Turing machine. See Conway's Game of Life for more details. Possibly because it was viewed as a largely recreational topic, little follow-up work was done outside of investigating the particularities of the Game of Life and a few related rules.

In 1969, however, Konrad Zuse published his book Calculating Space, proposing that the physical laws of the universe are discrete by nature, and that the entire universe is just the output of a deterministic computation on a giant cellular automaton. This was the first book on what today is called digital physics.

In 1983 Stephen Wolfram published the first of a series of papers systematically investigating a very basic but essentially unknown class of cellular automata, which he terms elementary cellular automata (see below). The unexpected complexity of the behavior of these simple rules—and the failure of mathematical methods to meaningfully describe them—lead Wolfram to suspect that complexity in nature may be due to similar mechanisms. Additionally, during this period Wolfram formulated the concepts of intrinsic randomness and computationally irreducibility, and suggested that rule 110 may be universal—a fact proved as part of the development of his later book.

Wolfram left academia in the mid-late 1980s to create Mathematica, which he then used to extend his earlier results to a broad range of other simple, abstract systems. In 2002 he published his results in the 1280-page text A New Kind of Science, which extensively argued that the discoveries about cellular automata are not isolated facts but are robust and have significance for all disciplines of science. Despite much confusion in the press and academia, the book did not argue for a fundamental theory of physics based on cellular automata, and although it did describe a few specific physical models based on cellular automata, it also provided models based on qualitatively different abstract systems.

The simplest cellular automata

The simplest nontrivial CA would be one-dimensional, with two possible states per cell, and a cell's neighbors defined as the cell on either side of it. A cell and its two neighbors forms a neighborhood of 3 cells, so there are 23=8 possible patterns for a neighborhood. So, there are 28=256 possible rules. These 256 CAs are generally referred to using a standard naming convention invented by Wolfram. The name of a CA is a number which, in binary, gives the rule table. For example, these are tables defining the "rule 30 CA" and the "rule 110 CA" and a graphical representation of them starting from a 1 in the center of the image:

File:CA rule30s.png
Rule 30 cellular automaton

current pattern 111 110 101 100 011 010 001 000
new state for center cell 0 0 0 1 1 1 1 0

File:CA rule110s.png
Rule 110 cellular automaton

current pattern 111 110 101 100 011 010 001 000
new state for center cell 0 1 1 0 1 1 1 0

A table completely defines a CA rule. For example, the rule 30 table says that if three adjacent cells in the CA currently have the pattern 100 (left cell is on, middle and right cells are off), then the middle cell will become 1 (on) on the next time step. The rule 110 CA says the opposite for that particular case.

If the columns are written in order as shown in the table above (the reverse order of counting in binary), then the number of the rule can be read off in binary. The bottom line in the first table has the bits 00011110, which is the binary representation of the number 30, so that CA is called the "rule 30 CA". Similarly, the rule 110 CA derives its name from 01101110, which is the binary representation of the decimal number 110.

A number of papers have analyzed and compared these 256 CAs. The rule 30 and rule 110 CAs are particularly interesting.

Rule 30 generates randomness despite the lack of anything that could reasonably be considered random input. Stephen Wolfram proposed using its center column as a pseudorandom number generator (PRNG), and despite occasional claims to the contrary, it passes every standard test for randomness, and Wolfram uses this rule in the Mathematica product for creating random integers. In particular in the 1990s a cryptography survey book claimed that rule 30 was equivalent to a linear feedback shift register (LFSR) but in fact the claim was about rule 90. Although Rule 30 produces randomness on many input patterns, there are also an infinite number of input patterns that result in repeating patterns. The trivial example of such a pattern is the input pattern only consisting of zeros. A less trivial example, found by Matthew Cook, is any input pattern consisting of infinite repetitions of the pattern '00001000111000', with repetitions optionally being separated by six ones.

Rule 110, like the Game of Life, exhibits what Wolfram calls Class 4 behavior, which is neither completely random nor completely repetitive. Localized structures appear and interact in various complicated-looking ways. In the course of the development of A New Kind of Science, Cook proved in 1994 that these structures were rich enough to support universality. This result is interesting because Rule 110 is an extremely simple one-dimensional system, and one which is difficult to engineer to perform specific behavior. This result therefore provides significant support for Wolfram's view that class 4 systems are inherently likely to be universal. Cook presented his proof at a Santa Fe Institute conference on Cellular Automata in 1998, but Wolfram blocked the proof from being included in the conference proceedings, as Wolfram did not want the proof to be published before the publication of A New Kind of Science. In 2004, Cook's proof was finally published in Wolfram's journal Complex Systems (Vol. 15, No. 1), over ten years after Cook came up with it.

Reversible cellular automata

A CA is reversible if and only if for every current configuration of the CA there is exactly one past configuration (preimage). If one thinks of a cellular automaton as a function mapping configurations to configurations, reversibility implies that this function is bijective.

For one dimensional CA there are known algorithms for finding preimages, and any 1D rule can be proved either reversible or irreversible. For CA of two or more dimensions it has been proved that the reversibility is undecidable for arbitrary rules. The proof by Jarkko Kari is related to the tiling problem by Wang tiles.

Reversible cellular automata are often used to simulate physical phenomena as gas and fluid dynamics, since they obey the laws of thermodynamics. Such CA have rules specially constructed to be reversible. Such systems have been studied by Tommaso Toffoli, Norman Margolus and others.

For finite CAs that are not reversible, there must exist patterns for which there is no previous state. These patterns are called Garden of Eden patterns. In other words, no pattern exists which will develop into a Garden of Eden pattern.

Several techniques can be used to explicitly construct reversible cellular automata with known inverses. Two common ones are the second order technique and the partitioning technique, both of which involve modifying the definition of a cellular automaton in some way. Although such automata do not strictly satisfy the definition of a cellular automaton given above, it can be shown that they can be emulated by a conventional CA with a sufficiently large neighborhood and number of states, and can therefore be considered a subset of conventional cellular automata.

Totalistic cellular automata

A special class of CAs are totalistic CAs. The state of each cell in a totalistic CA is represented by a number (usually an integer value drawn from a finite set), and the value of a cell at time t depends only on the sum of the values of the cells in the neighborhood (possibly including the cell itself) at time t-1. If the state of the cell at time t also depends on its state at time t-1, the CA is properly called outer totalistic, although the distinction is not always made. Conway's Game of Life is an example of an outer totalistic CA with cell values 0 and 1.

Uses in cryptography

Rule 30 was originally suggested as a possible stream cipher for use in cryptography.

Cellular automata have been proposed for public key cryptography. The one way function is the evolution of a finite CA whose inverse is hard to find. Given the rule, anyone can easily calculate future states, but it is very difficult to calculate previous states. However, the designer of the rule can create it in such a way as to be able to easily invert it. Therefore, it is a trapdoor function, and can be used as a public-key cryptosystem. The security of such systems is not currently known.

Related automata

There are many possible generalizations of the CA concept.

One way is by using something other than a rectangular (cubic, etc.) grid. For example, if a plane is tiled with equilateral triangles, those triangles could be used as the cells.

Also, the rules can be probabilistic rather than deterministic. The rule then gives, for each pattern at time t, the probability that the central cell will transition to each possible state at time t+1. Sometimes a simpler rule is used, such as, "The rule is the Game of Life, but on each time step there is a 0.001% probability that each cell will transition to the opposite color."

The neighborhood or rules could change over time or space. For example, initially the new state of a cell could be determined by the horizontally adjacent cells, but for the next generation the vertical cells would be used.

The grid can be finite, so that patterns can "fall off" the edge of the universe.

In CA, the new state of a cell is not affected by the new state of other cells. This could be changed so that, for instance, a 2 by 2 block of cells can be determined by itself and the cells adjacent to itself.

There are continuous automata. These are like totalistic cellular automata, but instead of the rule and the states being discrete (e.g., a table, using states {0,1,2}), continuous functions are used, and the states become continuous (usually values in [0,1]). The state of a location is a finite number of real numbers. Certain cellular automata can yield diffusion in liquid patterns in this way.

Other automata are described as being "continuous", where these have a continuum of locations. The state of a location is a finite number of real numbers. Time is continuous, and the state evolves according to differential equations. One important example is reaction-diffusion textures, differential equations proposed by Alan Turing to explain how chemical reactions could create the stripes on zebras and spots on leopards. When these are approximated by cellular automata, the CAs often yield similar patterns.

Cellular automata in nature

File:Textile cone.JPG
Conus textile with cellular automata pattern on its shell

Patterns of certain seashells, like the ones in Conus and Cymbiola genus, are generated by natural cellular automata. The pigment cells reside in a narrow band along the shell's lip. Each cell secretes pigments according to the activating and inhibiting activity of its neighbours, obeying a natural version of a mathematical rule. The cell band leaves the colored pattern on the shell as it slowly grows. For instance, the widespread species Conus textile bears a pattern resembling the Rule 30 CA described above.

Plants regulate their intake and loss of gases by using a cellular automaton model, each stoma on the leaf acting like a cell.

Articles on specific cellular automata

Cellular automata designed to enable self-replication

See also

References

External links


Error creating thumbnail: Unable to save thumbnail to destination
Wikibooks has more about this subject:

de:Zellulärer Automat fr:Automate cellulaire it:Automa cellulare ja:セル・オートマトン pl:Automat komórkowy ru:Клеточный автомат