|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)|
|Through your library||Configure|
Similar books and articles
Wolfgang Merzenich (1980). Cellular Spaces. Theoretical Medicine and Bioethics 1 (1):51-65.
R. Badii (1997). Complexity: Hierarchical Structures and Scaling in Physics. Cambridge University Press.
Hector Zenil (2013). What Is Nature-Like Computation? A Behavioural Approach and a Notion of Programmability. Philosophy and Technology:1-23.
Arto Salomaa (1985). Computation and Automata. Cambridge University Press.
Nir Fresco (2011). Concrete Digital Computation: What Does It Take for a Physical System to Compute? [REVIEW] Journal of Logic, Language and Information 20 (4):513-537.
Simon Y. Berkovich (1986). Mutual Synchronization in a Network of Digital Clocks as the Key Cellular Automation Mechanism of Nature: Computational Model of Fundamental Physics. Synopsis.
W. Schonbein (2005). Cognition and the Power of Continuous Dynamical Systems. Minds and Machines 15 (1):57-71.
David J. Chalmers (1994). On Implementing a Computation. Minds and Machines 4 (4):391-402.
Anouk Barberousse, Sara Franceschelli & Cyrille Imbert, Cellular Automata, Modeling, and Computation.
Pete Mandik (2008). Cognitive Cellular Automata. In Complex Biological Systems:. Icfai University Press.
Added to index2012-03-29
Total downloads41 ( #32,645 of 722,826 )
Recent downloads (6 months)5 ( #17,046 of 722,826 )
How can I increase my downloads?