Cellular Automata

'''Cellular Automata''' are regular arrays of identical finite state automata whose next state is determined solely by their 
current state and the state of their neighbours, usually by a boolean transition function. They are closely related to 
[[Random Boolean Network|Random Boolean Networks (RBN)]]. A CA contains many cells and each cell is a finite-state automaton 
connected to its neighbors - and so the whole machine or device is called a cellular automaton (pl. cellular automata). They 
were introduced by the mathematician John von Neumann in the 1950s as simple models of biological self-reproduction, and they 
are elementary models for [[Complex System|complex systems]] and processes consisting of a large number of simple, homogeneous, 
locally interacting components. 

== Definition ==

A suitable definition of [http://en.wikipedia.org/wiki/Cellular_Automata Cellular Automata] is according to [http://mathworld.wolfram.com/CellularAutomaton.html mathworld] the following statement: "A cellular automaton 
is a collection of colored cells on a grid that evolves through a number of discrete time steps according to a set 
of rules based on the states of neighboring cells." The two most common neighborhoods in the case of a 
two-dimensional cellular automaton on a square grid are the  
[http://mathworld.wolfram.com/MooreNeighborhood.html Moore neighborhood] (a square neighborhood) and the 
[http://mathworld.wolfram.com/vonNeumannNeighborhood.html von Neumann neighborhood] (a diamond-shaped neighborhood).

== Types ==

Stephen Wolfram proposed a classification of cellular automaton rules into four types, according to the results of evolving the system from a "disordered" initial state:

* I.  Evolution leads to a homogeneous state.
* II. Evolution leads to a set of separated simple stable or periodic structures.
* III. Evolution leads to a chaotic pattern.
* IV. Evolution leads to complex localized structures, sometimes long-lived.

David Epstein proposed a [http://www.ics.uci.edu/~eppstein/ca/wolfram.html classification] of cellular automaton rules into only three types:

* Contraction impossible
* Expansion impossible
* Both expansion and contraction possible

== Applets ==

Good Cellular Automata applets, including 1-dimensional CA and 2-dimensional CA where you can edit the rules online, can be found at the site [http://www.sussex.ac.uk/space-science/ca.html]. Rules with complex patterns are for instance Wolfram's [http://mathworld.wolfram.com/Rule30.html Rule 30] and or [http://mathworld.wolfram.com/Rule110.html Rule 110]. Mirek's Java Cellebration [http://psoup.math.wisc.edu/mcell/mjcell/mjcell.html MJCell] is a Java applet that allows playing 300+ Cellular Automata rules and 1400+ patterns. It can play rules from 13 CA rules families. A nice tutorial from David J. Eck about Cellular Automata and "the edge of chaos" can be found [http://math.hws.edu/xJava/CA/index.html here].

== Game of Life ==

[http://en.wikipedia.org/wiki/Conway's_Game_of_Life Conway's Game of Life] is one of the most popular two-dimensional CA.
It was invented by John H. Conway. The rules are very simple:

 '''Birth'''    If an unoccupied cell has 3 occupied neighbors, it becomes occupied.
 '''Survival''' If an occupied cell has 2 or 3 neighbors, the organism survives to the next generation.
 '''Death'''    If an occupied cell has 0..1 or 4..8 occupied neighbors, 
          the organism dies (0,1: of loneliness; 4-8: of overcrowding).

A description of the game can be found at the [http://mathworld.wolfram.com/Life.html mathworld] site.

Interactive Website by Paul Callahan: [http://www.math.com/students/wonders/life/life.html What is the Game of Life]

More about Conway's Game of Life :
http://www.tech.org/~stuart/life/rules.html

Interactive Essay: Exploring Emergence [http://llk.media.mit.edu/projects/emergence/life-intro.html The Facts of Life]

John Conway's Game of Life - Applet by Edwin Martin
[http://www.bitstorm.org/gameoflife/]

John Conway's Game of Life - Applet by Alan Hensel
[http://www.ibiblio.org/lifepatterns/]

== Larger than Life ==

Available in MJCell: Larger than Life
(an extension of the Game of Life to a larger radius or diameter)
[http://psoup.math.wisc.edu/mcell/mjcell/mjcell.html]

== Scientists ==

[http://en.wikipedia.org/wiki/Stephen_Wolfram Stephen Wolfram] is the author 
of the computer program Mathematica, the founder of Wolfram Research, and mainly 
known for his work about cellular automata.
Andrew Ilachinski works for the [http://www.cna.org/ Center for Naval Analyses (CNA)], USA.

Tommaso Toffoli is a Professor in the Electrical and Computer Engineering Department at Boston University. He has done a lot of work about Cellular Automata (CA), and a large parts of his CA work resembles Stephen Wolfram's and Edward Fredkin's approach to understand physical systems trough CA simulations. Some Publications can be found [http://pm1.bu.edu/~tt/publ.html here].

== References ==

* [http://cscs.umich.edu/~crshalizi/notebooks/cellular-automata.html C.R. Shalizi's Notebook Entry on CA]
* [http://mathworld.wolfram.com/CellularAutomaton.html Mathworld Entry for CA]
* [http://en.wikipedia.org/wiki/Cellular_automaton Main Wikipedia Entry for CA]
* [http://en.wikipedia.org/wiki/Conway's_Game_of_Life Main Wikipedia Entry for Conway's Game of Life]

== Books == 

There are two major books on Cellular Automata:

* Stephen Wolfram, ''A new kind of science'', Wolfram Media, Inc., 2002 [http://www.wolframscience.com/nksonline]
* Andrew Ilachinski, ''Cellular Automata: A Discrete Universe'', World Scientific, 2001, ISBN 9810246234

Other, less popular books:

* Tommaso Toffoli and Norman Margolus, ''Cellular Automata Machines: A New Environment for Modeling'', MIT Press, 1987, ISBN 0262200600
* Howard Gutowitz (editor), ''Cellular Automata: Theory and Experiment'', MIT Press, 1990, ISBN 0262570866