Design and application of convergent cellular automata

Abstract

Systems made of many interacting elements may display unanticipated emergent properties. A system for which the desired properties are the same as those which emerge will be inherently robust. Currently available techniques for designing emergent properties are prohibitively costly for all but the simplest systems.

The self-assembly of biological cells into tissues and ultimately organisms is an example of a natural dynamic distributed system of which the primary emergent behaviour is a fully operational being. The distributed process that co-ordinates this self-assembly is morphogenesis. By analysing morphogenesis with a cellular automata model we deduce a means by which this self-organisation might be achieved.

This mechanism is then adapted to the design of self-organising patterns, reliable electronic systems and self-assembling systems. The limitations of the design algorithm are analysed, as is a means to overcome them. The cost of this algorithm is discussed and finally demonstrated with the design of a reliable arithmetic logic unit and a self-assembling, self-repairing and metamorphosising robot made of 12,000 cells.