Lectures in Canada and Argentina
G. J. Chaitin
Spanish/English bilingual edition:
MIDAS, Valparaíso, Chile, 2011 Photo by Virginia Chaitin of lecture at Institute for Quantum Computing, 23 September 2009
Sans les mathématiques on ne pénètre point au fond de la
Sans la philosophie on ne pénètre point au fond des mathématiques.
Sans les deux on ne pénètre au fond de rien. --- Leibniz
[Without mathematics we cannot penetrate deeply into philosophy.
During September 2009, Greg Chaitin visited Ontario and delivered a series of six lectures as follows:
Chaitin delivered his lectures with a tremendous amount of enthusiasm and clarity, answering lots of interesting and challenging questions and engaging in vivid conversations and debates with students and researchers.
Those who were lucky enough to interact with him during lunches, dinners and coffee breaks will readily admit that it is a real delight to be in his presence. Chaitin likes to share his groundbreaking ideas and insights with anyone at any time.
During his Ontario tour of lectures, he presented topics for which he is well known, such as Algorithmic Information Theory, the discovery of his number Ω, complexity and incompleteness.
But he also discussed new ideas that are still in an embryonic state. In particular, he has been working for about a year in a new field that he calls Metabiology. The main idea of Metabiology, as Chaitin envisions it, is to describe a mathematical model of Biology, with the aim to give a mathematical proof of Darwin's Theory of Evolution. This mathematical model would be a toy one, to start with, so that one can prove theorems. Chaitin reported that he has proved 2 ½ theorems already and that he plans to continue in this direction. He invited whoever is interested to start working in this field. As it turns out, his number Ω (the halting probability), plays a role in Metabiology as well. More information on Metabiology can be found on his webpage http://www.umcs.maine.edu/~chaitin/.
Another one of Chaitin's characteristics became crystal clear throughout this series of lectures. During his 40+ years research career, he has gained a deep understanding and genuine appreciation of the work of such Masters as Leibniz, Borel, Weyl, Gödel, Turing and others.
He was accompanied by his wife who is an epistemologist with a special interest in pre-Socratic philosophy. On several occasions, he mentioned that he had been meaning to visit certain Institutes in Ontario, but that this had never materialized so far. On at least three occasions he met people that had corresponded with him over the years, but that he had never met in person.
This month of September, the Chaitin-in-Ontario series of 6 lectures was attended by full houses everywhere. Some talks are available as live stream video on-line. The audiences had the rare opportunity to meet and listen to one of the great thinkers of our time whose work is of profound interest in a number of different disciplines and of everlasting inspiration to subsequent generations.
Ilias Kotsireas, Wilfrid Laurier University, Waterloo, Canada, Chaitin-in-Ontario Lecture Series Organizer
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 a 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 Émile 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:
The first of these papers proposes an abstract, mutating software model of evolution, and the second paper gives this idea some mathematical substance, which I shall now describe.
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 book 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.
Gregory Chaitin, Valparaiso, December 2009
Mathematics, Complexity & Philosophy
G. J. Chaitin
Drawing by Marco Roblin
Gregory Chaitin is the discoverer of the remarkable Omega number --- which shows that God plays dice in pure mathematics --- and is now trying to create a general mathematical theory of biological evolution. He worked for many years at the IBM Watson Research Center in New York, has an honorary doctorate from the University of Córdoba in Argentina, and is an honorary professor at the University of Buenos Aires. He has also taught at the Instituto de Sistemas Complejos de Valparaíso in Chile, where he is Presidente Honorario del Comité Científico, and in the Programa de História das Ciências e das Técnicas e Epistemologia (HCTE) at the Universidade Federal do Rio de Janeiro (UFRJ). One of his books, MetaMat! Em Busca do Ômega, was published in São Paulo by Perspectiva in 2009.
[30 Jan 2011]