In this week’s podcast, “The Chaitin Interview IV: Knowability and Unknowability,” Walter Bradley Center director Robert J. Marks interviewed mathematician Gregory Chaitin on how he proved that the number that determines whether computer programs are elegant (in the sense of maximally efficient) is “unknowable.” As Dr. Chaitin explained in the segment published yesterday, any solution would be contradictory. Thus, his proof is a proof by contradiction.

By way of illustrating the concept of proof by contradiction, Dr. Marks then offered his proof by contradiction that “all positive integers — numbers like 6 or 129, or 10 ¹⁰⁰ — are interesting.”

This portion begins at 19:45 min. A partial transcript, Show Notes, and Additional Resources follow.

Robert J. Marks: If [some positive integers] are not interesting, there is a smallest, non-interesting number. But hey, that’s interesting!

Gregory Chaitin: Absolutely.

Robert J. Marks: That’s the proof by contradiction.

Gregory Chaitin (pictured): An uninteresting number would be one whose numerical value is irreducible. And that’s exactly the proof… That’s a very good explanation, because then the next step from that to my incompleteness theorem is to say, “Well, what does ‘interesting’ mean?”

And one good definition of “interesting” is: An interesting number is one that stands out because there is a more concise definition of it or, more precisely, a program that is substantially smaller than its numerical value that calculates it… that’s some way it stands out from the run-of-the-mill numbers. And the run-of-the-mill numbers are ones whose numerical value is an incompressible or irreducible string of bits. So you can sort of go step by step from that paradox about the smallest uninteresting number, which is, ipso facto, interesting, to a proof very similar to mine.

Note: “One of the most powerful types of proof in mathematics is proof by contradiction or an indirect proof. It is powerful because it can be used to prove any statement, in several fields of mathematics. The structure is simple: assume the statement to be proven is false, and work to show its falsity until the result of that assumption is a contradiction.” – “Proof by Contradiction (with Examples),” Tutors.com.

For example, Dr. Marks starts with the assumption that some positive integers are not interesting. He looks for evidence that the statement is false. He sees that there must be a smallest non-interesting positive integer. But even that integer is interesting by virtue of its smallness.

Next: Why human creativity is probably non-computable

Don’t miss the stories and links from the previous podcasts:

From Podcast 4:

Why the unknowable number exists but is uncomputable. Sensing that a computer program is “elegant” requires discernment. Proving mathematically that it is elegant is, Chaitin shows, impossible. Gregory Chaitin walks readers through his proof of unknowability, which is based on the Law of Non-Contradiction.

Getting to know the unknowable number (more or less). Only an infinite mind could calculate each bit. Gregory Chaitin’s unknowable number, the “halting probability omega,” shows why, in general, we can’t prove that programs are “elegant.”

From Podcast 3:

A question every scientist dreads: Has science passed the peak? Gregory Chaitin worries about the growth of bureaucracy in science: You have to learn from your failures. If you don’t fail, it means you’re not innovating enough. Robert J. Marks and Gregory Chaitin discuss the reasons high tech companies are leaving Silicon Valley for Texas and elsewhere.

Gregory Chaitin on how bureaucracy chokes science today. He complains, They’re managing to make it impossible for anybody to do any real research. You have to say in advance what you’re going to accomplish. You have to have milestones, reports. In Chaitin’s view, a key problem is that the current system cannot afford failure — but the risk of some failures is often the price of later success.

How Stephen Wolfram revolutionized math computing. Wolfram has not made computers creative but he certainly took a lot of the drudgery out of the profession. Gregory Chaitin also discusses the amazing ideas early mathematicians developed without the software-based methods we are so lucky to have today.

Why Elon Musk, and others like him, can’t afford to follow rules. Mathematician Gregory Chaitin explains why Elon Musk is, perhaps unexpectedly, his hero. Very creative people like Musk often have quirks and strange ideas (Gödel and Cantor, for example) which do not prevent them from making major advances.

Why don’t we see many great books on math any more? Decades ago, Gregory Chaitin reminds us, mathematicians were not forced by the rules of the academic establishment to keep producing papers, so they could write key books. Chaitin himself succeeded with significant work (see Chaitin’s Unknowable Number) by working in time spared from IBM research rather than the academic rat race.

Mathematics: Did we invent it or did we merely discover it? What does it say about our universe if the deeper mathematics has always been there for us to find, if we can? Gregory Chaitin, best known for Chaitin’s Unknowable Number, discusses the way deep math is discovered whereas trivial math is merely invented.

From the transcripts of the second podcast: Hard math can be entertaining — with the right musical score! Gregory Chaitin discusses with Robert J. Marks the fun side of solving hard math problems, some of which come with million-dollar prizes. The musical Fermat’s Last Tango features the ghost of mathematician Pierre de Fermat pestering the math nerd who solved his unfinished Last Conjecture.

Chaitin’s discovery of a way of describing true randomness. He found that concepts f rom computer programming worked well because, if the data is not random, the program should be smaller than the data. So, Chaitin on randomness: The simplest theory is best; if no theory is simpler than the data you are trying to explain, then the data is random.

How did Ray Solomonoff kickstart algorithmic information theory? He started off the long pursuit of the shortest effective string of information that describes an object. Gregory Chaitin reminisces on his interactions with Ray Solomonoff and Marvin Minsky, fellow founders of Algorithmic Information Theory.

Gregory Chaitin’s “almost” meeting with Kurt Gödel. This hard-to-find anecdote gives some sense of the encouraging but eccentric math genius. Chaitin recalls, based on this and other episodes, “There was a surreal quality to Gödel and to communicating with Gödel.”

Gregory Chaitin on the great mathematicians, East and West: Himself a “game-changer” in mathematics, Chaitin muses on what made the great thinkers stand out. Chaitin discusses the almost supernatural awareness some mathematicians have had of the foundations of our shared reality in the mathematics of the universe.

and

How Kurt Gödel destroyed a popular form of atheism. We don’t hear much about logical positivism now but it was very fashionable in the early twentieth century. Gödel’s incompleteness theorems showed that we cannot devise a complete set of axioms that accounts for all of reality — bad news for positivist atheism.

You may also wish to read: Things exist that are unknowable: A tutorial on Chaitin’s number (Robert J. Marks)

and

Five surprising facts about famous scientists we bet you never knew: How about juggling, riding a unicycle, and playing bongo? Or catching criminals or cracking safes? Or believing devoutly in God… (Robert J. Marks)

Show Notes

• 00:23 | Introducing Gregory Chaitin
• 00:40 | What is unknowability?
• 06:07 | Does non-computable mean unknowable?
• 09:43 | A simple explanation
• 21:34 | Is creativity non-computable?
• 25:55 | Defining creativity
• 28:19 | Panpsychism

Additional Resources

• Gregory Chaitin’s Website
• The Unknowable by Gregory Chaitin
• Unravelling Complexity: The Life and Work of Gregory Chaitin, edited by Shyam Wuppuluri and Francisco Antonio Doria
• Mathematica
• Paul Erdős, Hungarian mathematician
• Chaitin’s Constant
• Jack Schwartz, American mathematician
• Roger Penrose, British mathematician and Nobel Prize winner
• The Emperor’s New Mind by Roger Penrose
• Shadows of the Mind by Roger Penrose
• Stephen Hawking, British theoretical physicist
• Selmer Bringsjord, engineer and computer scientist
• The Lovelace Test, a discussion between Robert J. Marks and Selmer Bringsjord at Mind Matters
• Giulio Tononi, neuroscientist and psychiatrist
• Christof Koch, German-American neuroscientist
• David J. Chalmers, philosopher and cognitive scientist
• The Conscious Mind by David J. Chalmers
• Panpsychism
• Gottfried Wilhelm Leibniz’s monads
• “Consciousness and Information, Classical Quantum or Algorithmic?” by Gregory Chaitin
• Bit Bang. La nascita della filosofia digitale by Giuseppe O. Longo (translation: Bit Bang: The birth of digital philosophy)

Podcast Transcript Download