2013 Annual Science Report
University of Illinois at UrbanaChampaign Reporting  SEP 2012 – AUG 2013
Dynamics of SelfProgramming Systems
Project Summary
Living systems are unique in that they have the capacity to evolve. Evolving systems can reprogram themselves and so they are able to respond to perturbations by creating new functionality. This feature is something very different from physical systems, which obey a fixed or predetermined equation of motion. This project is a theoretical attempt to describe this state of affairs mathematically, and to construct computer programs that have the capacity to evolve and thus become more complex without this being “built in” by the original programmer.
Project Progress
The challenges to producing a mathematical and/or mechanistic model for the fundamentals of evolution all involve the fact that the very definition of evolvability does not fit the standard mathematical formalism of a dynamical system defined on a given, fixed space. The salient feature of evolvability is that a system can enlarge its state space, and the understanding of evolvability of a given evolutionary model must, at the very least, consider how a given model embeds into a more complex or higherdimensional model. More concretely, if we consider models where organisms adopt strategies, then evolvability corresponds not to a reordering or redistribution of previously existing strategies, but instead an innovation where novel strategies are added, which has the effect of increasing the dimension of the model. Again, the most important object of study here is how the lowerdimensional model embeds inside the higher — and the natural notion of structural stability is that dynamics be preserved in some coherent manner when a state space is enlarged.
We have started the exploration of these questions on standard evolutionary mathematical models and have shown that this stability with respect to enlargement ends up being completely different question than the standard question of stability. In particular, models that are evolutionarily stable in the classical sense are no longer so when one allows evolvability. We have catalogued several mathematical examples of this, and our next step is to consider a general theory of these embeddings.
Our work has primarily focused on two specific classes of examples: [1] Populations of individuals whose interactions can be described by cooperative game theory; and [2] Populations of individuals who interact through mathematical relationships encoded using recursive function theory.
Roughly speaking, [1] is formulated using replicator equations from game theory, but with an additional rule for evolution of the payoff matrix. Amongst the natural games to explore are ones where the gametheoretic payoffs are allowed to evolve in time, and do so in a “greedy” manner (roughly, players modify their payoffs in such a manner to optimize against the current state of the population). The challenges to producing a mathematical and/or mechanistic model for the fundamentals of evolution all involve the fact that the very definition of evolvability does not fit the standard mathematical formalism of a dynamical system defined on a given, fixed space. The salient feature of evolvability is that a system can enlarge its state space, and the understanding of evolvability of a given evolutionary model must, at the very least, consider how a given model embeds into a more complex or higherdimensional model. More concretely, if we consider models where organisms adopt strategies, then evolvability corresponds not to a reordering or redistribution of previously existing strategies, but instead an innovation where novel strategies are added, which has the effect of increasing the dimension of the model. Again, the most important object of study here is how the lowerdimensional model embeds inside the higher — and the natural notion of structural stability is that dynamics be preserved in some coherent manner when a state space is enlarged.
We have started the exploration of these questions on standard evolutionary mathematical models and have shown that this stability with respect to enlargement ends up being completely different question than the standard question of stability. In particular, models that are evolutionarily stable in the classical sense are no longer so when one allows evolvability. We have catalogued several mathematical examples of this, and our next step is to consider a general theory of these embeddings.
We considered the replicator equations from evolutionary population biology; these equations have the form that any species (or subspecies) grows with a rate proportional to their fitness assuming average interactions with all of the species in the model. More specifically, we write $\dot x_i = x_i (f_i(x) – F(x))$, where $f_i$ is the fitness of population $i$ against the rest of the system, and $F$ is the average fitness of any organism in the system. In short, species who are more fit than average will grow, and those less fit than average will decay. Moreover, the normal form of the replicator equation assumes that fitnesses are given by gametheoretic payoffs, i.e. the fitness is proportional to the average payoff a species will obtain by playing against a random opponent in the population.
We then considered two types of state space enlargements: the first is the case where extra species are added and the second is the case where the species are allowed to evolve on a timescale comparable to the timescale of the population dynamics.
In the first case, the prototypical example is to consider an $N$species model, then enlarge the state space to contain $N+1$species. Clearly, the behavior of the enlarged system will depend on the interactions between the new species and the original $N$ species, and one would like to understand the enlargement in the absence of this detailed information. The way to proceed is to postulate an ensemble of enlarged systems, where the ensemble is generated by some probability distribution, then determine the gross statistical properties of the ensemble of enlarged systems. We have shown that multiple behaviors are possible and all of these happen with some positive probability: for example, the introduction of a new species can have no effect on the original system (the introduced species dies out quickly), the introduced species can replace one or more of the species in the original model, or all $N+1$ species can find a coexisting equilibrium. We have shown numerically that this is robust to various parameters in the underlying $N$species system, and from this postulate that in general, any system of $N$ organisms is sensitive to certain types of incursions and insensitive to other types, and the probability of a random new organism being in either class is $O(1)$. In short, this finding says that ecosystems are always sensitive to some, but not all, evolutionary changes.
In the second case, we expanded the model by allowing the interaction functions to change on a timescale compatible to the timescale of the population dynamics — i.e. we allow for the payoffs in the fitness functions to change as well. This, in effect, corresponds to a dramatic enlargement of the phase space, since an $N$species model has $N(N+1)/2$ possible payoffs, this effectively makes the system go from $N$ to $N(N+3)/2$ dimensions. It is not hard to show that in the limit of arbitrarily slow evolution, the highdimensional system reduces to the lowdimensional system — i.e. if evolution is arbitrarily slow, it can be ignored. What we have shown numerically is that when we assume that the evolution is “greedy” , i.e. each organism modifies its payoffs in such a way to take the most advantage of the current fitness landscape, systems that are stable in this slow limit become unstable when the evolution parameter is taken large enough, and it seems the main mechanism for this instability is due to something similar to founder effects. But we note that there is a complex interaction between the structure of the underlying system and which species end up winning this battle, since it is not always true that the system runs in a winnertakeall manner. These are interesting, complex, and novel mathematical behaviors that we will investigate further.
To explain our work in [2], consider that in the world of biology, the most elementary agents that perform tasks (e.g. enzymes) are molecules. These molecules often act on other molecules and produce other molecules that can themselves act as agents. To mathematically model these systems, we can think of agents as functions. However, since the inputs and outputs of these agents can be agents themselves, we need to deal with a set of mathematical objects that are functions from the same set to itself. We hypothesize that this selfreferential property of biological systems is the source of the open ended growth of complexity and novelty generation. The mathematical model of a system of functions acting on functions is a dynamical system model based on the theory of recursive functions that can deal with this particular aspect of biological systems. Also, in order to test this hypothesis computationally, we are developing the simplest model programming language that is a pure metaprogramming language for itself, i.e. each program in this language takes other programs of the same kind as inputs and produces new programs based on those inputs. The structure of this programming language is designed analogously to the construction of recursive functions in recursive function theory. Then in our system, each agent will be a program in this language. At each time step, each program attempts to run with its neighbors as inputs, and if terminates successfully the inputs will be replaced by the resulting program. The goal of this project is to study the possibility of emergence of evolution of complexity from a dynamical system with the above property starting with an initial condition consisting of only simple objects.
This programming language is constructed using two types of objects: elementary functions and elementary operators. Elementary functions are the functions that are predefined in the language, and the elementary operators are the ones that can be used on functions to construct new functions. In classical recursion theory, the elementary functions are zero function (f(x) = 0), successor function (f(x) = x+1), and projection functions of various kinds. The first two functions are the defining functions for the set of natural numbers, while the latter is necessary to give functions of more than one variable access to their individual inputs. The elementary operators in classical recursion theory are combination of functions, recursion on functions, and unbounded search for the root of a function. Each computable function can be then written as a nested sequence of elementary operators on elementary functions. By listing the set functions constructed in this manner, we can assign each natural number a computable function. Then a program in our programming language will be some description of the nested list of operations on the elementary functions that describe the function of that program. Each agent is labeled by a natural number and the function associated with it and acts on other agents by the action of its function on the natural numbers of other agents. We have tried the classical recursion theory as our programming language, however, we were unable to observe any nontrivial interactions since the nonlocality in the action of the agents makes it very difficult for selection to happen in the runtime of the simulation. This is because the action of even the simplest functions such as the successor function on any function produces a new function that has no similarity with either of the original functions.
In order to overcome this problem, we are implementing a language that is a pure metaprogramming language for itself. In this language the elementary functions are chosen to be the defining structure of the functions themselves. The efficiency and completeness of this language depends on the choice of the elementary functions and operators respectively. We have chosen the combination function (f(g, h) = g o h), the branch functions (e.g. f1(g o h) = g, f2(g o h) = h), and projection functions as our elementary functions. The operators combination and search can easily be modified for the new system, but the work on finding the operator analogous to the recursion on these functions is still in progress. Once all the operators are set, if the resulting language is Turing complete (as is the original construct based on classical recursion theory), at least every deterministic dynamical system can be modeled by a particular set of programs and a set of rules on the order and frequency of action of those programs on each other. These rules can be based on spacedependent parameters playing the role environmental factors. This establishes a theoretical framework to study the possibility and the conditions under which those dynamical systems cross the inanimateliving boundary. Even though we have not proved that our constructed system, even under desirable conditions (if found), can undergo such transition in a reasonable simulation time, its welldefined mathematical structure, in principle, can be used to make prediction of this sort.

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