Life as Evolving Software
Gregory Chaitin: Life as Evolving Software. 2012.
Few people remember Turing’s work on pattern formation in biology (morpho- genesis), but Turing’s famous 1936 paper “On Computable Numbers. . . ” exerted an immense influence on the birth of molecular biology indirectly, through the work of John von Neumann on self-reproducing automata, which influenced Sydney Brenner who in turn influenced Francis Crick, the Crick of Watson and Crick, the discoverers of the molecular structure of DNA. Furthermore, von Neumann’s application of Turing’s ideas to biology is beautifully supported by recent work on evo-devo (evolutionary developmental biology). The crucial idea: DNA is multi-billion year old software, but we could not recognize it as such before Turing’s 1936 paper, which according to von Neumann creates the idea of computer hardware and software. We are attempting to take these ideas and develop them into an abstract fundamental mathematical theory of evolution, one that emphasizes biologi- cal creativity, inventiveness and the generation of novelty. This work is being published in two parts. Firstly a non-technical book-length treatment: G. Chaitin, Proving Darwin: Making Biology Mathematical to be published by Pantheon in 2012. There we explain at length the basic concepts and the history of ideas. For an overview of this book, a lecture entitled “Life as evolving software,” go to www.youtube.com and search for chaitin ufrgs. And in this paper we present a technical discussion of the mathematics of this new way of thinking about biology. More precisely, we present an information- theoretic analysis of Darwin’s theory of evolution, modeled as a hill-climbing algorithm on a fitness landscape. Our space of possible organisms consists of computer programs, which are subjected to random mutations. We study the random walk of increasing fitness made by a single mutating organism. In two different models we are able to show that evolution will occur and to characterize the rate of evolutionary progress, i.e., the rate of biological creativity. We call this new theory metabiology, and it deals with the evolution of mutating software and with random walks in software space. The mathematics we use is essentially Turing’s version of computability theory from the 1930s, including his colorful oracles, plus the idea of how to associate probabilities with computer programs utilized since the 1970s in algorithmic information theory, which is summarized in the appendix of this paper. It remains to be seen how far these ideas will go, but as is shown in this paper and in the companion volume , the first steps are encouraging. In our opinion, Turing’s ideas are of absolutely fundamental importance in biology, since biology is all about digital software.
 D. Berlinski, The Devil’s Delusion, Crown Forum, 2008.
 S. J. Gould, Wonderful Life, Norton, 1990.
 N. Shubin, Your Inner Fish, Pantheon, 2008.
 M. Mitchell, Complexity, Oxford University Press, 2009.
 J. Fodor, M. Piattelli-Palmarini, What Darwin Got Wrong, Farrar, Straus and Giroux, 2010.
 S. C. Meyer, Signature in the Cell, HarperOne, 2009.
 J. Maynard Smith, Shaping Life, Yale University Press, 1999.
 J. Maynard Smith, E. Szathm ́ary, The Origins of Life, Oxford University Press, 1999; The Major Transitions in Evolution, Oxford University Press, 1997.
 J. P. Crutchfield, O. G ̈ornerup, “Objects that make objects: The pop- ulation dynamics of structural complexity,” Journal of the Royal Society Interface 3 (2006), pp. 345–349.
 G. J. Chaitin, “Evolution of mutating software,” EATCS Bulletin 97 (February 2009), pp. 157–164.
 G. J. Chaitin, Mathematics, Complexity and Philosophy, Midas, in press. (See Chapter 3, “Algorithmic Information as a Fundamental Concept in Physics, Mathematics and Biology.”)
 G. J. Chaitin, “Metaphysics, metamathematics and metabiology,” in P. Garc ́ıa, A. Massolo, Epistemolog ́ıa e Historia de la Ciencia: Selecci ́ onde Trabajos de las XX Jornadas, 16 (2010), Facultad de Filosof ́ıa y Hu- manidades, Universidad Nacional de C ́ordoba, pp. 178–187. Also in APA Newsletter on Philosophy and Computers 10, No. 1 (Fall 2010), pp. 7–11, and in H. Zenil, Randomness Through Computation, World Scientific, 2011, pp. 93–103.
 G. Chaitin, Proving Darwin: Making Biology Mathematical, Pantheon, to appear.
 G. J. Chaitin, “A theory of program size formally identical to information theory,” J. ACM 22 (1975), pp. 329–340.
 G. J. Chaitin, Algorithmic Information Theory, Cambridge University Press, 1987.
 G. J. Chaitin, Exploring Randomness, Springer, 2001.
 C. S. Calude, Information and Randomness, Springer-Verlag, 2002.
 M. Li, P. M. B. Vit ́anyi, An Introduction to Kolmogorov Complexity and Its Applications, Springer, 2008.
 C. Calude, G. Chaitin, “What is a halting probability?,” AMS Notices 57 (2010), pp. 236–237.
 H. Steinhaus, Mathematical Snapshots, Oxford University Press, 1969, pp. 29–30.
 D. E. Knuth, “Mathematics and computer science: Coping with finiteness,” Science 194 (1976), pp. 1235–1242.
 A. Hodges, One to Nine, Norton, 2008, pp. 246–249; M. Davis, The Uni- versal Computer, Norton, 2000, pp. 169, 235.
 G. J. Chaitin, “Computing the Busy Beaver function,” in T. M. Cover, B. Gopinath, Open Problems in Communication and Computation, Springer, 1987, pp. 108–112.
 G. H. Hardy, Orders of Infinity, Cambridge University Press, 1910. (See Theorem of Paul du Bois-Reymond, p. 8.)
 D. Hilbert, “On the infinite,” in J. van Heijenoort, From Frege to G ̈ odel, Harvard University Press, 1967, pp. 367–392.
 J. Stillwell, Roads to Infinity, A. K. Peters, 2010.
 H. Rogers, Jr., Theory of Recursive Functions and Effective Computability, MIT Press, 1987. (See Chapter 11, especially Sections 11.7, 11.8 and the exercises for these two sections.)
 A. R. Meyer, D. M. Ritchie, “The complexity of loop programs,” Proceed- ings ACM National Meeting, 1967, pp. 465–469.
 C. Calude, Theories of Computational Complexity, North-Holland, 1988. (See Chapters 1, 5.)