Misplaced Pages

Cellular automaton: Difference between revisions

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Browse history interactively← Previous editNext edit →Content deleted Content addedVisualWikitext
Revision as of 14:41, 24 July 2003 editDysprosia (talk | contribs)28,388 editsmNo edit summary← Previous edit Revision as of 19:54, 1 August 2003 edit undo140.177.203.1 (talk) Added material about the importance of CAs. more info about rule 110, and m. cook. Fixed mistake about rule 30.Next edit →
Line 12: Line 12:
Cellular automata were invented by ] in his study of ]s. As a simplified model of the physics of our universe, he designed a two-dimensional CA with a small neighborhood (only cells that touch are neighbors), and with 29 states per cell. Within that universe, he designed an initial pattern which acted like a self-replicating machine, and mathematically proved that it would make endless copies of itself. Cellular automata were invented by ] in his study of ]s. As a simplified model of the physics of our universe, he designed a two-dimensional CA with a small neighborhood (only cells that touch are neighbors), and with 29 states per cell. Within that universe, he designed an initial pattern which acted like a self-replicating machine, and mathematically proved that it would make endless copies of itself.


Widespread interest in cellular automata started when ] invented the ]. This is a two-dimensional CA, with two states per cell, and where each cell has 8 neighbors. The rule is simple: 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. The universe typically starts with only a few black cells. This CA was very simple, yet allowed the construction of patterns that appeared to move themselves across the grid of cells. Life became the most widely-studied CA in history, and research on it continues. See ] for more details. In the 1970's a two-state, two dimensional cellular automaton named ] became very widely known, particularly among the early computing community. Invented by ], 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 occurence of gliders, which are arrangments 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 ].
See ] for more details.
{universal ]s, and self-replicating machines.}

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--and the relevance of cellular automata to general science remained unclear. In 1983 ] published the first of a series of papers systematically investigating a very basic but essentially unknown class of 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, and also is not amenable to traditional mathematical analysis. 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 1980's 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 <i>]</i>, which extensively argued that the discoveries about cellular automata are not isolated facts but are robust and have significance for all disciples 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.


In 2002, ] published the book <i>]</i>. It contains an analysis of one-dimensional cellular automata and proposes the thesis that physics should be modeled by cellular automata rather than by differential equations, on the grounds that cellular automata are simpler, yet still able to exhibit the complex phenomena seen in nature. It doesn't propose any particular cellular automaton for this.


=== The Simplest Cellular Automata === === The Simplest Cellular Automata ===
Line 76: Line 79:
A number of papers have analyzed and compared these 256 CAs. The rule 30 and rule 110 CAs are particularly interesting. 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. ] proposed using its center column as a ] (PRNG), and despite occasional claims to the contrary, it passes every standard test for randomness. (In particular in the 1990's a cryptography survey book claimed that rule 30 was equivalent to a ] (LFSR) but in fact the claim was really about rule 90.)
Wolfram proposed a ] (PRNG) based on rule 30. Rule 30 is run on a finite universe whose cells have random initial states, and the output is the sequence of states for one particular cell. He argued that since the rule is ''nonlinear'' (the rules cannot be written as equations using just XOR and NOT), the PRNG should be much better than a simple ] (LFSR). The rule 30 PRNG would therefore be more useful for both statistical and cryptographic applications, so he used this generator as the PRNG for ]. Unfortunately, the generator was later proved to be exactly equivalent to an LFSR, which renders it useless for cryptography and no better than an LFSR for statistical uses.


Rule 110, like the Game of Life, exhibits what Wolfram calls Class 4 behavior, which is neither completely random or completely repetative. Localized structures appear and interact in various complicated-looking ways. In the course of the development of <i>]</i>, ]'s research assistant ] proved that these structures were rich enough to support universality. This is an interesting result because Rule 110 is an extremely simple system, simple enough to suggest that naturally occuring physical systems may also be capable of universality--and hence questions about them will often be undecidable. This means they may not be amenable to closed-form mathematical solutions.
The rule 110 cellular automaton has interesting behavior, especially when the initial pattern is carefully chosen. Wolfram was the first to study it, and concluded that it obviously could not be ]. ] later proved it actually is Turing complete, and presented the proof at a ] conference, but Wolfram suppressed its publication with a court order. A general overview of the proof is given in Wolfram's book. This is an interesting result, because it shows that even the simplest cellular automata have all the computational power of a universal ]. It is not known which of these 256 simple CAs are Turing complete, other than rule 110 and the three other CAs trivially equivalent to it.

In violation of his Wolfram Research nondisclosure agreement, ] presented his proof before the publication of <i>]</i> at a ] conference. It was stripped from the proceedings by court order. Nevertheless the proof's existence became known, but no direct follow-on work was done because its significance was unclear outside the context of the intellectual structure for which it was developed. Since the publication of <i>]</i>, ] has been preparing a paper giving the complete proof, whose publication is pending.


=== Reversible Cellular Automata === === Reversible Cellular Automata ===
Line 88: Line 93:
=== Uses in Cryptography === === Uses in Cryptography ===


Rule 30 was originally suggested as a possible ] for use in ]. However, it was later broken, as described above. Rule 30 was originally suggested as a possible ] for use in ].


Cellular automata have been proposed for ]. The ] 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 ], and can be used as a public-key cryptosystem. The security of such systems is not currently known. Cellular automata have been proposed for ]. The ] 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 ], and can be used as a public-key cryptosystem. The security of such systems is not currently known.
Line 112: Line 117:


=== References === === References ===
* "History of Cellular Automata" from ]'s <i>A New Kind of Science</i>

* from the newsgroup comp.theory.cell-automata * from the newsgroup comp.theory.cell-automata
* von Neumann, John, 1966, ''The Theory of Self-reproducing Automata'', A. Burks, ed., Univ. of Illinois Press, Urbana, IL. * von Neumann, John, 1966, ''The Theory of Self-reproducing Automata'', A. Burks, ed., Univ. of Illinois Press, Urbana, IL.

Revision as of 19:54, 1 August 2003

A cellular automaton (plural: cellular automata) is a discrete model studied in computability theory and mathematics. 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 the same relative to each cell, 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. Each time the rules are applied 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 2 = 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. 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. 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 -- where t is the time step (vertical), and i is the index (horizontal) in one generation -- is xi-1, xi, xi+1, there are obviously going to be problems when a cell 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

Cellular automata were invented by John von Neumann in his study of self-replicating systems. As a simplified model of the physics of our universe, he designed a two-dimensional CA with a small neighborhood (only cells that touch are neighbors), and with 29 states per cell. Within that universe, he designed an initial pattern which acted like a self-replicating machine, and mathematically proved that it would make endless copies of itself.

In the 1970's 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 occurence of gliders, which are arrangments 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--and the relevance of cellular automata to general science remained unclear. In 1983 Stephen Wolfram published the first of a series of papers systematically investigating a very basic but essentially unknown class of 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, and also is not amenable to traditional mathematical analysis. 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 1980's 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 disciples 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 2=8 possible patterns for a neighborhood. So, there are 2=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 rule30.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 rule110.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.

The columns must be written in the given order (the reverse order of counting 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. (In particular in the 1990's a cryptography survey book claimed that rule 30 was equivalent to a linear feedback shift register (LFSR) but in fact the claim was really about rule 90.)

Rule 110, like the Game of Life, exhibits what Wolfram calls Class 4 behavior, which is neither completely random or completely repetative. Localized structures appear and interact in various complicated-looking ways. In the course of the development of A New Kind of Science, Stephen Wolfram's research assistant Matthew Cook proved that these structures were rich enough to support universality. This is an interesting result because Rule 110 is an extremely simple system, simple enough to suggest that naturally occuring physical systems may also be capable of universality--and hence questions about them will often be undecidable. This means they may not be amenable to closed-form mathematical solutions.

In violation of his Wolfram Research nondisclosure agreement, Matthew Cook presented his proof before the publication of A New Kind of Science at a Santa Fe Institute conference. It was stripped from the proceedings by court order. Nevertheless the proof's existence became known, but no direct follow-on work was done because its significance was unclear outside the context of the intellectual structure for which it was developed. Since the publication of A New Kind of Science, Matthew Cook has been preparing a paper giving the complete proof, whose publication is pending.

Reversible Cellular Automata

Sometimes it is possible to examine the state of a cellular automaton, and deduce the previous state. If the rules ensure that this is always possible, then the CA is called reversible. Given the rules, there is no general way to tell whether the CA is reversible. Jarkko Kari proved that this is undecidable for CAs with two or more dimensions. For CAs with one dimension, it is decidable.

For CAs that aren't 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, in one step, become a Garden of Eden pattern.

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 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.

See also:

References