A Simple Cellular Automation that Solves the Density and Ordering Problems

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.