Bio

In his native Brazil, Pedro P.B. de Oliveira holds the position of Adjunct Professor jointly at the School of Computer Science and the Post-Graduate Programme in Electrical Engineering, at Universidade Presbiteriana Mackenzie, São Paulo. His main research interests are cellular automata, applications of evolutionary computation, and computational aspects of artificial life. He traces his interest in NKS-related issues back to research carried out for his PhD from University of Sussex, UK. His thesis was on the two-dimensional cellular automaton (CA) designed by him to embody a fully self-contained artificial life world, capable of universal computation. From then on, his work remained concerned with the computational ability of CAs, and the possibility of designing those with a predefined computational behaviour by evolutionary means, coupled by an estimate of their dynamical behaviour. The topic addressed by his research during the Summer School was related to one such an ability, namely, CAs that would be able to perform well in the density classification task, that is, the ability to find out whether there are more 1s than 0s in the initial condition of a one-dimensional binary array.

Project: Still looking for good CA rules in the Density Classification Task

Context and motivation:

One of the most 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. The problem usually does not specify what should happen to the CA if the initial configuration has as many ones as zeros, although one could require (as sometimes happens in the literature) that, in this case, a specific final configuration also has to be achieved (for instance, a sequence of single 0s alternating with single 1s).

Although the DCT was proposed in 1978 [Gacs, Kurdyumov and Levin, 1978], it was not until 1995 that the problem, as formulated, was proven not to be possible [Land and Belew, 1995]. The n-ary case has also been proven later on that it has no solution either [Chau, Siu and Yan, 1999].

Before the original proof was derived a few 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 at 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 score of about 86%, considering CA lattices with odd lengths; the second best rule published in the literature is also due to these authors, its score being of about 85%. The fact is that, regardless of empirical and analytical efforts carried out during the last few years, the best imperfect rule for the DCT remains unknown.

Questions I asked:

During the Summer School I looked at ways that might help a deterministic search for better imperfect rules for the DCT than those currently known. Although I focussed on the radius 3 space, the radius 2 has also been probed. This objective was pursued with the following questions in mind:

Could good known DCT rules be used as an indication of the most promising regions of the search space?

In this context, I used a number of new rules recently found in my research group, all of them with a score that places them in between the two best known rules so far. The analyses I carried out show that there is at least one important feature that the good rules are exploiting so as to perform well on the DCT.

Could conservative rules in the search space provide an indication of regions to avoided during the search?

It turns out that a combination of results by [Fuks, 2000] and [Capcarrère and Sipper, 2001] entails that only conservative CAs can perform the DCT. So, the idea behind the question is that the conservative CA rules of the space could be regarded as beacons to be avoided, whenever one is trying to find good rules for the DCT. Although analyses were made using all conservative rules of the radius 2 space, no definite conclusion could yet be drawn in regard to how the notion of conservation should be used in searching for good DCT rules.

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.
• [Chau, Siu and Yan, 1999] H.F. Chau, L.W. Siu and K.K. Yan. “One dimensional n-ary density classification using two cellular automaton rules”. International Journal of Modern Physics C, 10(5):883-889, 1999.
• [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.

Favorite Three-Color Cellular Automaton

Rule Chosen: 981373591276

Reason: This rule has a very consistent appearance of absolute randomness with random initial conditions. With a single cell in any of the 3 states, the other cells being in any of the other 2 states, this rule has a nice overall look, suggestive of a pyramid, with 3 regions very clearly defined, 2 of them fully ordered regular domains, and the other completely disordered. This is interesting because there is a very consistent and dramatic contrast between its overall behaviour, comparing the two kinds of initial conditions, that is, while the temporal evolution is consistently random under random initial condition, it yields the consistent pyramid-like pattern under any single-cell initial condition.

Additional Information

de Oliveira, P. “Where Are the Good CA Rules for the Density Classification Task?” Presentation at NKS 2004, Boston, MA, 2004.