Where Are the Good CA Rules for the Density Classification Task?

Pedro Paulo Balbi de Oliveira
Mackenzie University

A widely studied computational problem in the context of cellular automata (CAs) is the so-called Density Classification Task (DCT, for short). In its standard formulation it states that a binary, one-dimensional CA has to converge to a final configuration of all cells in state 1, when the initial configuration has more 1s than 0s, and to a configuration of all 0s, whenever the initial configuration has more 0s than 1s. Although the DCT was proposed in 1978 [Gacs, Kurdyumov and Levin, 1978], it was not until 1995 that the solution of the problem, as formulated, was proven not to be possible [Land and Belew, 1995].

Before the original proof was derived a few research groups were trying to find a rule that could solve the DCT. However, with such a possibility precluded the search shifted towards looking for the rule that could solve the DCT as perfectly as possible. Using different search techniques, mostly evolutionary computation-based methods, various groups have put their methods to test, and over time good rules have been found. For historical reasons, the search methods employed have been scanning the huge radius 3, 2-state CA space, the best rule found so far being due to Juillé and Pollack [1998], with a correct classification score of about 86%. The fact is that regardless of empirical and analytical efforts carried out during the last years, the best imperfect rule for the DCT remains unknown.

Our concern herein is on ways that might help a search for better imperfect rules for the DCT than those currently known. And this is done by trying to answer the following questions: could good, known DCT rules be used as an indication of the most promising regions of the search space?; and, could conservative rules in the search space provide an indication of regions to be avoided during the search? These questions are addressed by relying on analyses of good, known rules from radius 3 space and on a search carried out in the radius 2 space.      

References:
[Capcarrère and Sipper, 2001] M.S. Capcarrère and M. Sipper. “Necessary conditions for density classification by cellular automata.” Physical Review E, 64(3):036113/1-036113/4, 2001.

[Fuks, 2000] H. Fuks. “A class of cellular automata equivalent to deterministic particle systems.” In: S. Feng, A.T. Lawniczak and S.R.S. Varadhan, eds. Hydrodynamic limits and related topics, Amer. Math. Soc., Providence, RI, USA, 57-69, 2000.

[Gacs, Kurdyumov and Levin, 1978] P. Gacs, G.L. Kurdyumov and L.A. Levin. Problemy Peredachi. Informatsii, 14:92-98, 1978.

[Juillé and Pollack, 1998] H. Juillé and J.B. Pollack. “Coevolving the ‘ideal’ trainer: Application to the discovery of cellular automata rules.” In: J.R. Koza, W. Banzhaf, K. Chellapilla, M. Dorigo, D.B. Fogel, M.H. Garzon, D.E. Goldberg, H. Iba and R.L. Riolo (eds.). Genetic Programming 1998: Proceedings of the Third Annual Conference, San Francisco, CA: Morgan Kaufmann, 1998.

[Land and Belew, 1995] M.W.S. Land and R.K. Belew. “No two-state CA for density classification exists”. Physical Review Letters, 74(25):5148-51, 1995.

Created by Mathematica  (April 20, 2004)