# Evolution and Turing Machines

I haven’t made any headway on the Grey Lady’s Top 100 Books of the Year, partly because I’ve been too busy reading what comes down the arXivotubes. For example, take Giovanni Feverati and Fabio Musso’s recent e-print, “An evolutionary model with Turing machines” (arXiv:0711.3580, 22 November).

The development of a large non-coding fraction in eukaryotic DNA and the phenomenon of the code-bloat in the field of evolutionary computations show a striking similarity. This seems to suggest that (in the presence of mechanisms of code growth) the evolution of a complex code can’t be attained without maintaining a large inactive fraction. To test this hypothesis we performed computer simulations of an evolutionary toy model for Turing machines, studying the relations among fitness and coding/non-coding ratio while varying mutation and code growth rates. The results suggest that, in our model, having a large reservoir of non-coding states constitutes a great (long term) evolutionary advantage.

Taking the broad view, it’s interesting that a large mass of genetic information might not directly code for phenotypic features while still having a long-term adaptive advantage. (Thinking about fitness over multiple generations gives me a headache: the mapping from phenotype to fitness value isn’t constant over time. Cluster a whole bunch of predators together, and they kill off all the prey, changing their environment and thereby making their own phenotype unfit. Some people really care about this; I just know it makes me want to go back to neutrino physics.) A few details of note:

First, Feverati and Musso evolve their Turing machines to specified goals: they want a machine which ends its operation with a tape containing a particular sequence of zeros and ones. In different trials, two distinct goal tapes were used, a tape representing the first 100 prime numbers and a tape holding the bits after the radix point in the binary expansion of π. (These goals were chosen in part because a periodic distribution is an easy thing for a Turing machine to make. I suppose we’re talking about maximizing Kolmogorov complexity, though the authors don’t make that connection explicitly.)

Second, the only form of mutation in their simulation was point mutation. More specifically, they randomly changed each entry in a Turing machine’s description with some probability $$p_{\rm m}$$. Gene duplication and other such mechanisms were not implemented. States are added with a certain probability $$p_{\rm i}$$ per timestep; these states are non-coding until a point mutation elsewhere establishes a call to them.

UPDATE (28 November): A real biologist offers comments below. The number of people who know more than I do about any given subject is awfully impressive!

UPDATE (1 December): More here.

## 8 thoughts on “Evolution and Turing Machines”

1. The result here is interesting, but it’s always been at least implicit in the evo-comp literature that I’ve read that the advantage of “code-bloat” was that it allowed a greater degree of variation in the populations of optimization solutions. I think this relates somewhat to Fisher’s theorem.

2. Yeah, makes sense. (I’ve used genetic algorithms for cracking open inverse problems, but I could probably be better read in the evo-comp literature than I am.) I’d be curious to see if one could do this sort of thing without a fixed target: while there is a kind of “morphological” step in between the genotype (TM state table) and the phenotype (tape content at halting time), getting away from fixed target tapes might provide a better analogy to real biology.

3. Some observations:
– “Proof by model” is not convincing to me, ever.
– Long-term benefit is not how evolution works, although there could be inter-lineage selection of a sort (I discussed this here: http://genomicron.blogspot.com/2007/06/inter-lineage-selection-versus-just-in.html)
– More non-coding DNA is associated with higher risk of extinction, higher sensitivity to pollution, exclusion from harsh climates, and lower species richness per clade.
– The onion test:
http://genomicron.blogspot.com/2007/04/onion-test.html

4. Many thanks!

I recall the “Onion Test,” though I must have missed your post on inter-lineage selection the first time around.

5. windy says:

It’s somehow amusing that the link says “EvolutionBeyondNeoDarwin[ism]”, while the actual title is significantly more modest… pounced on by reviewers?

I’m still skeptical of this kind of extreme beyond-everything-so-far group selection argument (I’m trying to think of a term to distinguish it from D.S. Wilson’s brand? ‘The new new group selection’?) But I’ll have to look into it some more. I’ll just point out that people do look at variation in fitness between generations from the individual organism point of view (geometric mean fitness, bet-hedging). At the very least, the authors could have explained why these would not apply in the predator case?

…itâ€™s always been at least implicit in the evo-comp literature that Iâ€™ve read that the advantage of â€œcode-bloatâ€ was that it allowed a greater degree of variation in the populations of optimization solutions. I think this relates somewhat to Fisherâ€™s theorem.

If that’s the reason, wouldn’t we expect faster evolution in big-genomed organisms? Which doesn’t seem to be the case.

6. The most buzzwordy term I’ve thought of yet is “emergent group selection.” I mean, who doesn’t like “emergence”?

7. “If thatâ€™s the reason, wouldnâ€™t we expect faster evolution in big-genomed organisms? Which doesnâ€™t seem to be the case.”

I’m not competent to assess its applicability to biology, but in optimization problems of the sort I’m talking about algorithms usually operate in pre-defined search spaces and with fixed targets. That could mitigate other factors in biological evolution that prohibit too much genomic “bloat”, but I don’t know for sure.