Cellular Automata

From CasGroup

Jump to: navigation, search

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 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 systems and processes consisting of a large number of simple, homogeneous, locally interacting components.

Contents

Definition

A suitable definition of Cellular Automata is according to 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 Moore neighborhood (a square neighborhood) and the 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 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 [1]. Rules with complex patterns are for instance Wolfram's Rule 30 and or Rule 110. Mirek's Java Cellebration 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 here.

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

Interactive Website by Paul Callahan: 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 The Facts of Life

John Conway's Game of Life - Applet by Edwin Martin [2]

John Conway's Game of Life - Applet by Alan Hensel [3]

Larger than Life

Available in MJCell: Larger than Life (an extension of the Game of Life to a larger radius or diameter) [4]

Scientists

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

References

Books

There are two major books on Cellular Automata:

  • Stephen Wolfram, A new kind of science, Wolfram Media, Inc., 2002 [5]
  • 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
Personal tools