nai

Project Progress

To mathematically model the self-referential property of biological systems that is responsible for the growth of complexity in evolution, we had previously designed and implemented a simple model programming language that is a pure metaprogramming language for itself. In this language, every program is an instruction set for processing the computational tree of other programs written in this language. In this way, the dynamics of programs acting on each other can model the dynamics of molecular agents acting on each other undergoing a prebiotic chemical evolution. After optimization and design considerations, we have discovered that our language is equivalent to the SKI model of computation. SKI is a Turing complete model of computation constructed from three elementary operations, S, K, and I. This model is used in computer science to study the limit of computation of programming languages, and is of particular interest in theoretical studies due to its extreme simplicity. Other variations of SKI have been previously used in artificial chemistry models and are shown to be capable of producing self-maintaining structures known as organizations [1, 2]. We have mathematically defined the “open-ended growth of complexity” as formation of a hierarchy of higher order organizations. In conclusion, we have developed a mathematical framework to study if the self-referential property of the biological system is a sufficient condition for the open-ended growth of complexity or not.

We have proposed a second self-referential model for evolution of complexity. This model consists of a pair of unconventional cellular automata each of which encodes the list of local update rules for the other. In this model, not only is the global update rule not limited to the conventional 256 update rules, but also this global rule is not constant in time; the same dynamics that is responsible for the evolution of the states of the system is also responsible for the evolution of the update rules. The coevolving pair of cellular automata are defined as following: We start with two arrays of cells, each cell in one of the two states labeled with zero and one. At each time step, to update each cell, we read the 8 digits following the corresponding cell in the other cellular automaton. These digits encode one of the 256 rules of the elementary cellular automata that we use as the local rule to update the aforementioned cell. Then, to update the twin automata containing the update rules for current automata, we repeat the same procedure using the current automata to obtain the update rules. There are two advantages in this model. There is a natural mapping from the 8 digit state to the rule space (the 8 digits can be readily read as a number indexing the rules). Also, since each cell has its own rule, the total update rule of the grid is not restricted to the 256 rules. We have shown that the total information entropy content of the pair of coevolving cellular automata increases monotonically with time.

[1] P. S. di Fenizio and W. Banzhaf, “A less abstract artificial chemistry,” Artificial Life, vol. 7, pp. 49-53, 2000.
[2] P. S. di Fenizio, P. Dittrich, and W. Banzhaf, “Spontaneous formation of proto-cells in an universal artificial chemistry on a planar graph,” in Advances in artificial life, pp. 206-215, Springer, 2001.