Sipper, M. and Capcarrere, M. and Ronald, E. (1998) A Simple Cellular Automation that Solves the Density and Ordering Problems. International Journal of Modern Physics C, 9 (7). pp. 899-902.
Cellular automata (CA) are discrete, dynamical systems that perform computations in a distributed fashion on a spatially extended grid. The dynamical behavior of a CA may give rise to emergent computation, referring to the appearance of global information processing capabilities that are not explicitly represented in the system's elementary components nor in their local interconnections.1 As such, CAs o�er an austere yet versatile model for studying natural phenomena, as well as a powerful paradigm for attaining �ne-grained, massively parallel computation. An example of such emergent computation is to use a CA to determine the global density of bits in an initial state con�guration. This problem, known as density classi�cation, has been studied quite intensively over the past few years. In this short communication we describe two previous versions of the problem along with their CA solutions, and then go on to show that there exists yet a third version | which admits a simple solution.
|Uncontrolled keywords:||Cellular Automata; Density Problem; Emergent Computation|
|Subjects:||Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,|
|Divisions:||Faculties > Science Technology and Medical Studies > School of Computing > Applied and Interdisciplinary Informatics Group|
|Depositing User:||Mark Wheadon|
|Date Deposited:||24 Aug 2009 16:33|
|Last Modified:||06 Sep 2011 03:59|
|Resource URI:||http://kar.kent.ac.uk/id/eprint/21594 (The current URI for this page, for reference purposes)|
- Depositors only (login required):