Cellular automata

Stanford Encyclopedia of Philosophy (2012)
  Copy   BIBTEX

Abstract

Cellular automata (henceforth: CA) are discrete, abstract computational systems that have proved useful both as general models of complexity and as more specific representations of non-linear dynamics in a variety of scientific fields. Firstly, CA are (typically) spatially and temporally discrete: they are composed of a finite or denumerable set of homogeneous, simple units, the atoms or cells. At each time unit, the cells instantiate one of a finite set of states. They evolve in parallel at discrete time steps, following state update functions or dynamical transition rules: the update of a cell state obtains by taking into account the states of cells in its local neighborhood (there are, therefore, no actions at a distance). Secondly, CA are abstract, as they can be specified in purely mathematical terms and implemented in physical structures. Thirdly, CA are computational systems: they can compute functions and solve algorithmic problems. Despite functioning in a different way from traditional, Turing machine-like devices, CA with suitable rules can emulate a universal Turing machine, and therefore compute, given Turing's Thesis, anything computable....

Links

PhilArchive

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Cellular spaces.Wolfgang Merzenich - 1980 - Theoretical Medicine and Bioethics 1 (1):51-65.
Computation and Automata.Arto Salomaa - 1985 - Cambridge University Press.
Concrete Digital Computation: What Does it Take for a Physical System to Compute? [REVIEW]Nir Fresco - 2011 - Journal of Logic, Language and Information 20 (4):513-537.
On implementing a computation.David J. Chalmers - 1994 - Minds and Machines 4 (4):391-402.

Analytics

Added to PP
2012-03-29

Downloads
169 (#76,276)

6 months
13 (#73,664)

Historical graph of downloads
How can I increase my downloads?