In last week’s podcast,, “The Chaitin Interview V: Chaitin’s Number,” Walter Bradley Center director Robert J. Marks continued his conversation with mathematician Gregory Chaitin, best known for Chaitin’s unknowable number. Last time, they looked at how Chaitin’s unknowable number relates to computer pioneer Alan Turing’s vexing halting problem in computer science. This time, they look at the way pure mathematics has a way of being highly practical: It creates a basis for new understanding, leading to technical breakthroughs:
This portion begins at 09:50 min. A partial transcript, Show Notes, and Additional Resources follow.
Gregory Chaitin: There are always going to be a few of us who like to do practical things. That’s part of my personality too, but there’s also, in me, a side that likes beautiful mathematical arguments and these fantasy worlds of pure mathematics, which has this strange number glowing there, the Omega number. We do need some people who do pure mathematics with no applications, at least maybe not for a hundred years. People who think philosophically, and I think Omega is a stimulus.
It’s nice to have this number. I didn’t expect it to catch on the way it did. I wouldn’t say it’s complicated because I invented it. But it takes a mathematical theory that is non-trivial, to understand exactly how you define the number and why it has the properties it does. I thought the business that you can’t prove that a program is elegant would catch on more but people are interested in philosophical questions. Even though Omega is sort of a unicorn or a flying horse, — a mathematical fantasy in the Platonic world of ideas — it’s caught on. That shows that we all have a taste for that kind of question too, which is good.
The human spirit is capable of doing both things. Practical things and impractical things which may have practical consequences later.
Robert J. Marks: An instance of that is encryption involving large prime numbers and their factorization, which is used in most of the encryption used today. That was a mathematical theorem that lay around for a long time before somebody found out that, “Hey, we could use this for encryption purposes!”
Gregory Chaitin: Yeah. Who would have thought that? G. H. Hardy loved number theory because he said it’s purest of the pure, pure mathematics. He has a book that was written during the Second World War, I think. He’d seen the First World War and he hated things with practical applications because he said they would be used for carnage, for slaughter. He said, at least there’s one subject which will forever be as pure as the driven snow, because it’s totally impractical, which is number theory. Now it’s used for cryptography, for sending military messages probably. I don’t know.
Robert J. Marks: Absolutely. Yes.
Note: Earlier, Gregory Chaitin commented: And people don’t write books. In the past, some wonderful mathematicians like G. H. Hardy (1877–1947) would write wonderful books like A Mathematician’s Apology (1940) or his book on number theory (1938).
Hardy was the mathematician who received gifted young mathematician Srinivasa Ramanujan’s letter from India and “ in 1914, Hardy brought Ramanujan to Trinity College, Cambridge, to begin an extraordinary collaboration.” Ramanujan (1887–1920) was prompted to write to Hardy after reading one of his books. (MacTutor)
Ramanujan was plagued by ill health and Hardy recounted at one point: “I remember once going to see him when he was lying ill at Putney. I had ridden in taxi cab number 1729 and remarked that the number seemed to me rather a dull one, and that I hoped it was not an unfavourable omen. ‘No,’ he replied, ‘it is a very interesting number; it is the smallest number expressible as the sum of two cubes in two different ways.”
On broader issues, Hardy also said, “I believe that mathematical reality lies outside us, that our function is to discover or observe it, and that the theorems which we prove, and which we describe grandiloquently as our ‘creations,’ are simply the notes of our observations.” – A Mathematician’s Apology. So he seems akin to those who think that mathematics is discovered, not invented.
Gregory Chaitin: It’s used also for banks, financial transactions. Hardy would probably be very disappointed, but historically, it’s fun. The same thing happens with algorithmic information theory.
At least for me, it was purely philosophical. I was interested in incompleteness. I was interested in more practical stuff, but it looked very difficult. And now what is it? Algorithmic information theory goes back to the 60s. What are we now?
It’s 60 years later. Hector McNeil and his collaborators are using practical approximations to this ideal theory and for practical applications.
Oh, this is the biggest joke of all: The halting probability Omega is totally unknowable. It’s uncomputable, but you can calculate it in the limit from below. You look at more and more programs, you see which ones hold and that way, the halting probability keeps going up, your estimate keeps going up. But it’s very, very slow this process. But in the limit of infinite time, you can calculate it in the limit from below.
Well, the joke is that Hector McNeil has proposed using this as a new cryptocurrency that he calls Automacoin. This is a serious proposal because Bitcoin, the most popular cryptocurrency, uses an immense amount of computing power. Really scary amount of computing power that didn’t even exist before. But it’s all going for this. It’s not terribly useful computation except for financial transactions. But what Hector’s Neil has basically proposed is to calculate the bits of Omega in the limit from below.
This gives you a cryptocurrency where what you calculate is very, very useful. It’s useful in the way that Marvin Minsky pointed out, that it tells you the best theories for things. The most concise programs with things. That can be used for making predictions.
Robert J. Marks: Well, one of the interesting things about this, talking to George Gilder, an economics guru and a forecaster of the future, is that one of the problems with Bitcoin is that the amount of value that you can get out of it is fixed. There’s only a certain amount of gold that can be mined from Bitcoin software. If we use the Omega number as a basis for a cryptocurrency, there would be no limit, would there? It would just get harder and harder to mine the gold.
Gregory Chaitin: Right. The further you go. And the results of those computations are actually useful. Whereas in Bitcoin, you’re spending a very, very large amount of computing power mining Bitcoins. And it’s only useful for Bitcoins.
It’s not useful for anything else. Hector thinks that’s a terrible waste. At any rate, I think it’s a… I’m not terribly interested in practical applications, not when I’m thinking about mathematics and Omega and everything. but the fact that it proposed as a new cryptocurrency, I think is fantastic. It’s just a lot of fun. Who would have guessed?
But you have to wait 60 years though. When I was publishing these papers, if I had to do practical work, I wouldn’t have been able to do that research. 60 years later, this is practical research based on the Omega number.
Next: Could Chaitin’s Number prove the Goldbach conjecture?
Don’t miss the stories and links from the previous podcasts:
From Podcast 5:
Chaitin’s number talks to Turing’s halting problem. Why is Chaitin’s number considered unknowable even though the first few bits have been computed? Chaitin explains, after you have computed some of the numbers, all the rest looks totally random and unstructured and you’ll never know them.
Is Chaitin’s unknowable number a constant? One mathematics team has succeeded in the first 64 bits of a Chaitin Omega number. Gregory Chaitin explains that it’s more complicated than that; it depends on whether you use a universal Turing machine that allows for very concise programs.
From Podcast 4:
Can mathematics help us understand consciousness? Gregory Chaitin asks, what if the universe is information, not matter? Some philosophers see the universe as created by mathematics, not matter. Gregory Chaitin prefers to see it as created by information. God is then a programmer.
Why human creativity is not computable. There is a paradox involved with computers and human creativity, something like Gödel’s Incompleteness Theorems or the Smallest Uninteresting Number. Creativity is what we don’t know. Once it is reduced to a formula a computer can use, it is not creative any more, by definition.
The paradox of the first uninteresting number. Robert J. Marks sometimes uses the paradox of the smallest “uninteresting” number to illustrate proof by contradiction — that is, by creating paradoxes. Gregory Chaitin: You can sort of go step by step from the paradox of the smallest “uninteresting” number to a proof very similar to mine.
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.
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)
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)
- 00:27 | Introducing Gregory Chaitin and Chaitin’s number
- 01:32 | Chaitin’s number or Chaitin’s constant?
- 07:16 | Must the halting problem be solved for smaller programs in order to get Chaitin’s number?
- 09:50 | The usefulness of philosophy and the impractical
- 17:17 | Could Chaitin’s number be calculated to a precision which would allow for a proof or disproof of something like Goldbach’s Conjecture?
- 19:20 | The Jump of the Omega Number
- Gregory Chaitin’s Website
- Unravelling Complexity: The Life and Work of Gregory Chaitin, edited by Shyam Wuppuluri and Francisco Antonio Doria
- Elements of Information Theory by Thomas Cover and Joy Thomas
- “On the length of programs for computing finite binary sequences,” by Gregory Chaitin, published when he as a teenager. (Journal of the ACM (JACM) 13, no. 4 (1966): 547-569).
- Chris Calude, professor at the University of Auckland
- Gottfried Wilhelm Leibniz, German Enlightenment philosopher, mathematician, and political adviser
- Stephen Wolfram, computer scientist and physicist
- Goldbach Conjecture
- Collatz Conjecture
- Legendre’s Conjecture
- Elon Musk, engineer and entrepreneur
- G.H. Hardy, English mathematician
- Ray Solomonoff, one of the founders of algorithmic information theory
- Hector Zenil, computational natural scientist
- Marvin Minsky, cognitive and computer scientist
- George Gilder, economist and co-founder of the Discovery Institute
- Twin Prime Conjecture
- Georg Cantor, mathematician
- BBC 4’s Dangerous Knowledge