A Simple Cellular Automation that Solves the Density and Ordering Problems

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. (Full text available)

PDF
Download (248kB)
[img]
Preview
Official URL
http://dx.doi.org/10.1142/S0129183198000868

Abstract

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 > 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):

Downloads

Downloads per month over past year