The story of how I became interested in computability and randomness is in my essay in Calude, Randomness and Complexity, from Leibniz to Chaitin, World Scientific, 2007. There is also a shorter version in another book in the 5 questions series: Floridi, Philosophy of Computing and Information, Automatic Press, 2008. So I shall not discuss that here.
My main concern over the years, besides originally helping to create the field of program-size complexity, which I like to call algorithmic information theory, has been the new light that program-size complexity throws on incompleteness. Program-size complexity is now a well-developed, mature field, especially when it comes to the complexity of individual strings, but perhaps not in the case of the complexity of enumerating infinite sets.
One of my concerns has been to find randomness in different areas of pure mathematics: starting with the halting probability Ω, then dressing up the bits of Ω in terms of diophantine equations, and more recently by using the word problem and Wang tiles.
All of my information-theoretic incompleteness results depend on measuring the complexity of a formal axiomatic theory via the size in bits of a self-delimiting program for enumerating all the theorems of that theory. This complexity measure may seem too naive and too abstract, but it yields a number of powerful incompleteness theorems. Based on this work, I have proposed a quasi-empirical view of mathematics which encourages experimental mathematics and working the way theoretical physicists do. Not surprisingly, these proposals have not met with favor in the math community, but have attracted attention in the physics community.
I have collected all my essays on this subject in Thinking about Gödel and Turing, also published by World Scientific in 2007. In these essays I attempted to make as convincing a case as possible, and linked these ideas to the work of Leibniz and the French mathematician Emile Borel.
Since program-size complexity and its applications to metamathematics is now, in my opinion, a mature field, my gaze is turning elsewhere: to biology. The idea of looking at the size of a computer program may not seem like much, but in the course of half a century it has developed into a rich field. I am now playing with another simple idea which could conceivably be equally fertile: the evolution of mutating software.
I discuss this in two recent papers in the Bulletin of the European Association for Theoretical Computer Science:
Here's the basic idea: We consider an extremely simple model of evolution, consisting of a single software "organism" that computes a single positive integer. The larger the positive integer, the fitter the organism. We try a mutation at random. If the resulting software organism outputs a larger positive integer, then the mutation is accepted; otherwise it is rejected. With a little care, we can arrange things in such a manner that our mutating software describes a random walk in software space of ever increasing fitness. In fact, the output of our software organism will grow faster than any computable function of its size in bits, which shows that genuine creativity is occurring.
Here is what is happening: Usually small changes in the software will give small, incremental improvements in fitness, e.g.,
But eventually the random walk will try larger changes or additions, and find extremely concise ways to name gigantic positive integers. In doing this there is unlimited scope for creativity, since it is equivalent to trying to solve the halting problem.
That's the basic idea of how our toy model works, and it is merely a first step in the direction of an abstract theory of evolution. What I really want is a statistical theory of software evolution that characterizes the kind of structure that mutating program software organisms are likely to have. Programs obtained by constant tinkering, by what the French call bricolage, are very different from those that are written from scratch. Can we statistically characterize that difference? And how much does it depend on the choice of programming language or the way we perform the random mutations?
I would like to encourage readers of this essay to study mutating software models. It will no doubt take many years of work by many people to develop a proper theory of random walks in software space. How biologically relevant all of this is remains to be seen, but I am hopeful that fifty years from now, when we celebrate the two-hundredth anniversary of On the Origin of Species, we shall have a general, abstract mathematical theory of evolution. Perhaps even sooner.
[February 24, 2009]