2014 Annual Science Report
University of Illinois at UrbanaChampaign Reporting  SEP 2013 – DEC 2014
Project 1: Dynamics of SelfProgramming Systems
Project Summary
This project is a theoretical attempt to understand how evolution can arise from inanimate physical systems. The key idea is that matter can organize into structures that not only replicate and carry information, but are able to program and reprogram themselves functionally. We have already been able to construct simple computer programs that can increase their complexity in an openended way, but in this grant period we have been building a mathematical formulation of how this arises using recursive function theory. We have also been trying to develop cellular automata metaprogramming pairs that can coevolve complexity.
Project Progress
To mathematically model the selfreferential 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 selfmaintaining structures known as organizations [1, 2]. We have mathematically defined the “openended growth of complexity” as formation of a hierarchy of higher order organizations. In conclusion, we have developed a mathematical framework to study if the selfreferential property of the biological system is a sufficient condition for the openended growth of complexity or not.
We have proposed a second selfreferential 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. 4953, 2000.
[2] P. S. di Fenizio, P. Dittrich, and W. Banzhaf, “Spontaneous formation of protocells in an universal artificial chemistry on a planar graph,” in Advances in artificial life, pp. 206215, Springer, 2001.

PROJECT INVESTIGATORS:

PROJECT MEMBERS:
Nigel Goldenfeld
Project Investigator
Elbert Branscomb
CoInvestigator
Lee DeVille
CoInvestigator
Tommaso Biancalani
Collaborator
Farshid Jafarpour
Collaborator

RELATED OBJECTIVES:
Objective 3.2
Origins and evolution of functional biomolecules
Objective 4.1
Earth's early biosphere.
Objective 4.2
Production of complex life.
Objective 5.3
Biochemical adaptation to extreme environments
Objective 6.2
Adaptation and evolution of life beyond Earth