Skip to main content

A Simple Cellular Automation that Solves the Density and Ordering Problems

Sipper, Moshe, Capcarrere, Mathieu S., 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:10.1142/S0129183198000868) (KAR id:21594)

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
DOI/Identification number: 10.1142/S0129183198000868
Uncontrolled keywords: Cellular Automata; Density Problem; Emergent Computation
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Mark Wheadon
Date Deposited: 24 Aug 2009 16:33 UTC
Last Modified: 16 Nov 2021 09:59 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/21594 (The current URI for this page, for reference purposes)

University of Kent Author Information

Capcarrere, Mathieu S..

Creator's ORCID:
CReDIT Contributor Roles:
  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.