Computability, Gödel's incompleteness theorem, and an inherent limit on the predictability of evolution

Abstract

The process of evolutionary diversification unfolds in a vast genotypic space of potential outcomes. During the past century, there have been remarkable advances in the development of theory for this diversification, and the theory's success rests, in part, on the scope of its applicability. A great deal of this theory focuses on a relatively small subset of the space of potential genotypes, chosen largely based on historical or contemporary patterns, and then predicts the evolutionary dynamics within this pre-defined set. To what extent can such an approach be pushed to a broader perspective that accounts for the potential open-endedness of evolutionary diversification? There have been a number of significant theoretical developments along these lines but the question of how far such theory can be pushed has not been addressed. Here a theorem is proven demonstrating that, because of the digital nature of inheritance, there are inherent limits on the kinds of questions that can be answered using such an approach. In particular, even in extremely simple evolutionary systems, a complete theory accounting for the potential open-endedness of evolution is unattainable unless evolution is progressive. The theorem is closely related to Gödel's incompleteness theorem, and to the halting problem from computability theory.

Figure 1.

A schematic of the coding of population states, and the theorem. The middle irregular shape represents the space of population states, S, with four states depicted (the ovals). Roman numerals indicate the time when each state is visited during evolution (the silver-shaded state, s = {T,T,T}, is never visited). Vertical ovals on the right and left represent two different codings by the positive integers, along with their respective evolutionary mappings, ϕ_E(n) and , over the first three time steps. If evolution is progressive, then coding 2 is possible, and the theorem then says that we can ‘decide’ any population state, s ∈ S. For example, we can decide state ‘T,T,T’ by finding its code (i.e. ‘1’), and then iterating the map, , until we obtain an output greater than ‘1’ (this occurs at time step 1 because ). If ‘1’ has not yet been visited by this time, it never will be. Conversely, if all population states are decidable, then, under coding 1, we can apply the algorithm provided in part 2 of the theorem's proof to obtain coding 2, thereby demonstrating that evolution is progressive.

Figure 2.

A schematic of the relationship between the biological process of evolution and theory. The example given illustrates classical population-genetic theory. A formal system is created to represent elements of evolution (e.g. p(t) represents the number of the blue genotype at time t). A set of premises is specified (e.g. initial genotype numbers, how genotypic fitnesses are determined, etc.—this is embodied by the mapping F). Rules of deduction are then followed (e.g. repeated application of the mapping F) to obtain new statements about elements of the formal theory (e.g. p(1); p(2); p(3), etc.). These new elements are then interpreted in terms of evolution (e.g. as predictions about genotype numbers at future times).