[NKS 2004: Pedro de Oliveira, Where Are the Good CA Rules for the Density...] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


NKS 2004: Pedro de Oliveira, Where Are the Good CA Rules for the Density...

(Click here to view the original thread with full colors/images)


Posted by: Catherine Boucher

Pedro de Oliveira
Mackenzie University
Where Are the Good CA Rules for the Density Classification Task?

Session:
10:30am, April 23, 2004, Eden Vale A
Pure NKS: The Study of Simple Programs
Part 1: General Features of Cellular Automata

Abstract:

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.

http://www.wolframscience.com/confe...s/index_49.html

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.



Posted by: Tony Smith

I just stumbled back into this thread while doing some research into what increasingly appears to be to be an overinterpretation of a 1993 paper by Melanie Mitchell, Peter Hraber and James Crutchfield which appears to have only really set out to question Packard's evidence for Chris Langton's problematic proposal for a linear characterisation of CA rule space (which he called lambda) with which the phase transition between order and chaos (c.f. Wolfram's Class 4) was supposed to take not just a persistent value, but a value converged to by evolution (tested using genetic algorithms).

In their paper, Mitchell et al actually said:
The results presented here do not disprove the hypothesis that computational capability can be correlated with phase transitions in CA rule space. Indeed, this general phenomena has already been noted for other dynamical systems. More generally the computational capacity of evolving systems may very well require dynamical properties characteristic of phase transitions if they are to increase their complexity. We have shown only that the published experimental support cited for hypotheses relating (Langton's lambda) and computational capability in CA was not reproduced.
but the community at large seems to have mistakenly taken this as implying that any search for the border of order/edge of chaos was unlikely to be fruitful.

The Density Classification Task (DCT) was the problem used by both Packard and Mitchell et al to test the notion of lambda. The measuring stick for this two colour one dimensional problem is the 1978 Gacs-Kurdyumov-Levin (GKL) rule with 7 neighbours and thus a rule space of 2**(2**7), far too big to be searched exhaustively. Neither Packard nor Mitchell et al got close to GKL performance although more recent claims have been made for marginal improvements over GKL both through human design and genetic algorithms.

But it looks to me that the DCT might be an especially problematic test, seeing that it seeks differentiation at exactly that 50% threshold which coincides with a sharp combinatorial peak in the rule space. Surely this level of numeric precision is not the kind of task that evolution would need to cope with in the natural world.




Forum Sponsored by Wolfram Research

© 2004-2009 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings