The Unknowable by Gregory Chaitin

Gregory Chaitin’s The Unknowable is billed as the companion volume to his Limits of Mathematics, though it also, in many ways stands on its own. In this work, Chaitin sets out to explain the way that his work follows from Godel’s Incompleteness Theorem and Turing’s Halting Problem.

The story begins with the mathematician David Hilbert pioneering the field of metamathematics as a way to eliminate all doubts about the efficacy and power of mathematics. However, this process ultimately failed, instead revealing the fundamental uncertainty that underlies mathematics. However, the result of this failure was a large role in the development of the modern computer and other resulting technologies! Chaitin characterizes this as a most spectacular failure.

Bertrand Russell’s set theory paradoxes  led to the development of symbolic logic, which via Godel and Turing, showed that it is impossible to formalize mathematics and further that “essentially any formal axiomatic system is either inconsistent or incomplete,” (p. 11). Chaitin, from an early age, became intrigued in these problems and wanted to determine if these problems were unusual or if they impacted all of math:

I began to suspect that perhaps sometimes the reason that mathematics can’t figure out what’s going on is because nothing is going on, because there is no structure, there is no mathematical pattern to be discovered. Randomness is where reason stops, it’s a statement that things are accidental, meaningless, unpredictable, and happen for no reason (p. 22).

And ultimately, through his work on randomness, is what Chaitin has come to assert, in a way that neatly parallels contemporary quantum physics.

Chaitin then uses the programming language LISP to create proofs for both the Incompleteness Theorem and the Halting Problem, before developing his own proof related to algorithmic information theory: “Roughly speaking, a random string is incompressible, there is no simple theory for it, its program-size complexity is as large as possible for bit strings have that length,” (p. 86). This, Chaitin argues, is even stronger than Turing’s proof because it goes beyond saying something cannot be computed, and shows that it cannot be proven. The book features the LISP code that can be used to construct these proofs for those who are interested:

Finally, somewhat surprisingly in the conclusion of the book, but perhaps most interestingly for my own work, is the argument that we might better understand information as primary – is the “software” that can be run on a variety of different hardware. Examples include the same information that can be represented in materially different ways through DNA, DVDs, videotapes, nerve impulses, and hormones, to name a few. The material becomes irrelevant and what matters primarily is information.