Cellular automaton: Difference between revisions

Revision as of 17:42, 7 February 2007

Revision as of 13:10, 8 February 2007

Line 10:

==History==

[[Stanislaw Ulam]], while working at the [[Los Alamos National Laboratory|Los Alamos]] National Laboratory in the 1940s, studied the growth of crystals, using a simple [[Lattice model (physics)|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 system]]s. 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_cellular_automataVon Neumann cellular automata|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's 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 [[Conway's Game of Life|Game of Life]] became very widely known, particularly among the early computing community. Invented by [[John Horton Conway|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]].

Line 122:

Some living things use naturally occurring cellular automata in their functioning.

Patterns of some [[seashell]]s, like the ones in ''[[Cone snail|Conus]]'' and ''[[Cymbiola]]'' genus, are generated by natural CA. The [[pigment]] cells reside in a narrow band along the shell's lip. Each cell [[secretion|secretes]] pigments according to the activating and inhibiting activity of its neighbour pigment cells, obeying a natural version of a mathematical rule.{{factFact|date=February 2007}} The cell band leaves the colored pattern on the shell as it grows slowly. For example, the widespread species ''[[Conus textile]]'' bears a pattern resembling the Rule 30 CA described above.

Plants regulate their intake and loss of gases via a CA mechanism. Each [[Stomata|stoma]] on the leaf acts as a cell.

Line 201:

*[http://geneffects.com/evita/ Open source Java code and application for multiple state CA on 2D lattice]

*[http://falconnet.peddie.org/students/2007/nburoojy/projects/cellular/ All 256 CA Rules] - 256 pictures of one dimensional CA.

{{Wikibookspar||Cellular Automata}}