 | Cellular automaton: Encyclopedia II - Cellular automaton - History of cellular automata
Cellular automaton - 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; 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 stays or becomes white. Despite its simplicity, the system achieves an impressive diversity of behavior, fluctuating between apparent randomness and order. One of the most apparent features of the Game of Life is the frequent occurrence of gliders, 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. 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 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 computational 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.
Other related archives1969, 1970s, 1980s, 1983, 1990s, 1994, 1998, 2002, 2004, A New Kind of Science, A. K. Dewdney, Alan Turing, Belousov-Zhabotinsky reaction, Bootstrapping, Calculating Space, Codd's Cellular Automaton, Conus, Conway's Game of Life, Day & Night, Excitable medium, Game of Life, Garden of Eden patterns, HighLife, Immigration, John Conway, John von Neumann, Konrad Zuse, Langton's ant, Lights Out (game), Los Alamos, Martin Gardner, Mathematica, Matthew Cook, Oscillator, Puffer train, QuadLife, Santa Fe Institute, Scientific American, Seeds, Spaceship, Stanislaw Ulam, Stephen Wolfram, Tommaso Toffoli, Turing machine, Universal Constructor, Wang tiles, Wireworld, [0, 1], bijective, computability theory, continuous automata, cryptography, digital physics, discrete, lattice network, linear feedback shift register, mathematics, one way function, orthogonal, partitioning technique, pigment, preimage, preimages, pseudorandom number generator, public key cryptography, rule 110, rule 110 CA, seashells, second order technique, secretes, self-replicating systems, stoma, stream cipher, tessellation, theoretical biology, thermodynamics, tiled, torus, trapdoor function, undecidable, universal, universal copier and constructor, zebras
 Adapted from the Wikipedia article "History of cellular automata", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki |
