A Simple Cellular Automation that Solves the Density and Ordering Problems

Sipper, Moshe and Capcarrere, Mathieu S. and Ronald, Edmund M. A. (1998) A Simple Cellular Automation that Solves the Density and Ordering Problems. International Journal of Modern Physics C, 9 (7). pp. 899-902. (doi:https://doi.org/10.1142/S0129183198000868 ) (Full text available)

Download (147kB) Preview
Official URL


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.

Item Type: Article
Uncontrolled keywords: Cellular Automata; Density Problem; Emergent Computation
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Faculties > Sciences > School of Computing > Applied and Interdisciplinary Informatics Group
Depositing User: Mark Wheadon
Date Deposited: 24 Aug 2009 16:33 UTC
Last Modified: 28 Jun 2017 16:26 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/21594 (The current URI for this page, for reference purposes)
  • Depositors only (login required):