Authors
Franz Berto
University of St. Andrews
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....
Keywords Mereology  Digital Physics  Non-Standard Computation  Complexity Theory
Categories (categorize this paper)
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,316
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Time and Chance.David Z. Albert - 2000 - Harvard University Press.

View all 35 references / Add more references

Citations of this work BETA

Proof Systems for Exact Entailment.Johannes Korbmacher - forthcoming - Review of Symbolic Logic:1-37.
Causation in a Virtual World: a Mechanistic Approach.Billy Wheeler - 2022 - Philosophy and Technology 35 (1):1-26.

View all 9 citations / Add more citations

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 index
2012-03-29

Total views
156 ( #76,176 of 2,519,292 )

Recent downloads (6 months)
7 ( #100,736 of 2,519,292 )

How can I increase my downloads?

Downloads

My notes