Algorithmic Chemistry: A Model for Functional Self-Organization

Walter Fontana

90-011

We conjecture that adaptive systems are characterized by a self-referential loop in which combinatorial objects encode functions that act back on these objects. A model for this loop is presented. It uses a simple and powerful recursive language to map character strings into algorithms that symbolically manipulate strings. The interaction between algorithms, i.e., functions, can be defined in a natural way within the language. The behavior of a fixed size ensemble of functions acting on each other is studied under various conditions. The "function gas," or "Turing gas," evolves cooperative interaction patterns of considerable intricacy. Such patterns are observed to adapt under the influence of perturbations consisting in the addition of new random functions to the systems. Completely different organizational architectures emerge depending on the availability of self-replicators.