Interview with Gregory Chaitin
Consistent systems are “boring;” paradoxes are fertile.
We are once again honored to interview an intellectual giant of our time. A polymath of a rare breed, the contributions of Gregory Chaitin go beyond publishing pioneering research in reputable journals to leading an intellectual movement that is likely to last for generations.
Born in 1947 in Chicago, Chaitin attended City College of New York, where, at the age of 15, he independently discovered what is now known as Algorithmic Information Theory. The Dean excused him from attending classes to prepare the paper for publication, for which the College awarded him a gold medal, the Belden Mathematical Prize, and later the Nehemiah Gitelson award for “the search for truth.”
Like many free thinkers throughout history, Chaitin preferred adventurous self-learning to formal education. His only formal degree is a high school degree from the NYC Bronx High School of Science. However, his revolutionary insights have earned him widespread acclaim within the scientific community. He was awarded two honorary doctorates, one in computer science and one in philosophy, in recognition of his seminal contributions. He spent much of his professional career at IBM Thomas J. Watson Research, and he held visiting professorship positions at several leading universities. In the list of his “heroes,” Gottfried Wilhelm Leibniz holds a high rank. In 2007 he was awarded the Leibniz Medallion by Wolfram Research. He is also a lifetime honorary professor of the University of Buenos Aires, Argentina, and is currently in residence at the Institute for Advanced Study, University Mohammed VI Polytechnic (UM6P), Benguerir, Morocco.
He is best known for Chaitin’s Incompleteness Theorem and for the halting probability Omega, also known as Chaitin’s number, an example of irreducible complexity in pure mathematics. He has also proposed a new field, Metabiology, to study the random evolution of computer programs rather than DNA. A detailed list of his papers and books can be found on his personal website.
GL: You are a pioneer of Algorithmic Information Theory (AIT). We are now witnessing a major transition from the Age of Information to the Age of Artificial Intelligence (AI). How relevant is AIT to the age of AI?
GC: I prefer to talk about algorithms 1.0, traditional software, and algorithms 2.0, neural nets. AIT applies to algorithms 1.0. For algorithms 2.0, I feel that traditional Shannon information theory — not AIT—and statistical mechanics and thermodynamics are more relevant, but I am not an expert on algorithms 2.0.
GL: You propose the hypothesis: “All is algorithm. God is a Programmer.” This hypothesis is sometimes used in favor of the argument that we live in a computer simulation. Some recent papers suggest that the chances that our universe is a pure simulation are 50–50. What do you think?
GC: I do not think that we live in a computer simulation, unless it is a simulation in the mind of God. A computer capable of simulating the universe would have to be bigger than the universe.
A computer capable of simulating the universe would have to be bigger than the universe.
GL: The prominent mathematician André Weil famously remarked: “God exists since mathematics is consistent, and the Devil exists since we cannot prove it.” Do you think undecidability can be useful in bridging the gap between logic and ethics, between passion and reason?
GC: My views are different. Exaggerating a bit, consistent mathematics is boring, because I believe in the fertility of paradox. For example, it is paradoxical for finite man to attempt to comprehend God, who is infinite. But it is worth trying. Furthermore, not everything is provable.
It is paradoxical for finite man to attempt to comprehend God, who is infinite. But it is worth trying.
GL: According to your theory, “understanding is compression.” By understanding a phenomenon, we are able to explain it (and predict it) using a concise law that is substantially less complex (in terms of bits of information) than the phenomenon. But how does the human mind arrive at this understanding? Is this process of understanding more complex than the concerned phenomenon itself?
GC: I do not know how the human mind arrives at understanding. If I did, I could build an artificial general intelligence (AGI), the holy grail of current AI research. I hope the process of understanding is not more complex than the concerned phenomenon, because if so the human brain will never understand how the human brain works.
GL: The quote attributed to Einstein, “The most incomprehensible thing about the world is that it is comprehensible,” might indicate that the process of “comprehending” (i.e., compressing) might be a highly complex process …?
GC: Leibniz has an explanation: This is the best of all possible worlds, in the sense that God maximizes the richness and diversity of the world, and simultaneously minimizes the ideas, the bricks, the mathematical laws, that He uses to build this world. Hence the world is comprehensible, as part of God’s perfection. This is in the Discours de métaphysique.
GL: Einstein reportedly said: “Everything should be made as simple as possible but not simpler.” You define an “elegant program” to be the smallest program (in terms of bits of information) that can produce a given output. Within a formal axiomatic system of size N bits, you show that it is possible to find all elegant programs of size less than N. Can we consider finding such “elegant programs” a formalization of Einstein’s dictum?
GC: What I think Einstein means is that we search for beautiful (simple) theories, but some phenomena are not simple, and will require more complicated theories.
GL: You told a story of your interaction with Gödel. He mentioned to you (and it is in his paper) that: “Every epistemological antinomy can likewise be used for a similar undecidability proof.” Since there is possibly an unlimited number of such antinomies, does that mean there would be potentially an unlimited number of undecidability theorems?
GC: Every theorem has an infinite number of possible proofs. The goal should be to find the simplest, most natural proof, or as Grothendieck might put it, the context that makes the proof trivial. I believe I have found the natural context for thinking about incompleteness.
Every theorem has an infinite number of possible proofs.
GL: Your approach to incompleteness is based on information rather than on a Liar-like paradox used by Gödel. You argue that this new viewpoint suggests that the incompleteness phenomenon is natural and widespread rather than pathological and unusual. Does that mean incompleteness is not confined to formal axiomatic systems? Is it possible to detect incompleteness or undecidability in informal systems (although in such “informal systems,” there would be no systematic way to detect or identify incompleteness)?
GC: Mathematical incompleteness theorems apply only to formal axiomatic systems. In the real world, some systems are closed and do not evolve, i.e. have stagnated, and others are open-ended and creative. I prefer that latter, not the former. In other words, incompleteness is good, not bad.
GL: You show that, in a formal axiomatic system, no information can be formally derived from the system that is larger in complexity than that of the axioms of the system (plus a constant). In other words, we cannot, in principle, derive more information from the system than the system has. Is this a kind of “conservation law of information”?
GC: Yes it is a kind of conservation law, of mathematical information.
The information incompleteness theorem is a kind of conservation law of mathematical information.
GL: Gödel’s second incompleteness theorem dictates, roughly, that the consistency of a consistent system cannot be asserted within the system. In other words, the system’s consistency shall be “invisible” within the system, or otherwise, the system will become inconsistent. What is the informational counterpart of this result? Put differently, AIT produces the information equivalent of Gödel’s First Incompleteness Theorem. What is the information equivalent of the Second Theorem?
GC: There is no informational equivalent of Gödel’s second incompleteness theorem. In my opinion, only Gödel’s first incompleteness theorem is fundamental. The second incompleteness theorem was a historical accident because Hilbert and Brouwer were arguing about the validity of non-constructive proofs, and Hilbert wished to convince Brouwer that at least they would never produce inconsistencies.
There is no informational equivalent of Gödel’s second incompleteness theorem.
GL: According to mathematician Edward Frenkel, modern science made the “observer” integral to scientific theory. For example, quantum mechanics has shown that the observer is always involved in the observation. Likewise, Gödel’s incompleteness theorem shows how essential the observer of a mathematical theory is; for that is the one who chooses the axioms. (I might add that the observer can decide the consistency of the system, which cannot be asserted within the system.) Likewise, in Einstein’s relativity, time is relative to the observer. What is the role of the “observer” in AIT? Is this role key for the “empirical mathematics” you propose?
GC: The observer in AIT is metamathematics, which studies the power and the limitations of formal axiomatic theories from above, from the outside, as it were.
GL: Mathematical physicist Eugene Wigner wrote: “The miracle of the appropriateness of the language of mathematics for the formulation of the laws of physics is a wonderful gift which we neither understand nor deserve.” How do you see the relationship between mathematics and the real world?
GC: I disagree with Wigner. I believe that mathematics is the ontological basis of reality. God is a mathematician. As Leibniz said, as God cogitates and calculates, so the world is made. That is my view of the relationship between mathematics and reality.
Mathematics is the ontological basis of reality.
GL: Many thanks for your helpful and insightful answers!
GC: Thank you for your stimulating questions!
