Density Classification


Principal Investigator

Timothy Cranny

School of Information Technology

Charles Sturt University


Terry Bossomaier

School of Information Technology

Charles Stuart University


h06 - VPP

We are investigating the role of intrinsic structure
in emergent computation (computation which
emerges from a system composed of simpler entities). We have recently discovered that all known examples of this phenomenon share a certain mathematical structure. The set of all examples with this structure forms an extremely small subset of the total space, so a search for new results inside this subspace is far more powerful and efficient than a search of the unconstrained space. We have used a genetic algorithm to examine this subspace, and are now analysing and categorising the data produced.



What are the results to date and the future of the work?

We have found a multitude of new high-performance cellular automata rules for emergent computation, and have found a number of regularities in the results obtained. A number of papers are in preparation, and we have developed the theoretical infrastructure necessary to extend and explain the work completed.

What computational techniques are used?

The algorithm used is highly vectorisable, and requires a vast number of simple operations to be repeated many times. We are using a genetic algorithm to evolve cellular automata rules, and as is typical in such cases the vast majority of the computational requirements comes in the process of assessing fitness. In this case it requires thousands of cellular automaton rules be assessed, each against several hundred initial conditions and run for several hundred timesteps.

- Appendix B