Mind Matters Natural and Artificial Intelligence News and Analysis

# Is Chaitin’s Unknowable Number a Constant?

One mathematics team has succeeded in the first 64 bits of a Chaitin Omega number
Share
Flipboard
Print
Email

In this 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. In this segment, Dr. Marks and Dr. Chaitin discuss whether the unknowable number is really a number… or is it a constant? In earlier podcasts linked below, they have discussed a variety of topics ranging from gifted mathematicians of the past through how to understand creativity in a mathematical way—and more.

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

Robert J. Marks (pictured): I want to clear up something first of all. Stanford’s Thomas Cover and Joy Thomas wrote a book that I used as a textbook for the graduate course in information theory called Elements of Information Theory. They refer to Chaitin’s “magical mystery number,” Omega. This is in a very thick, scholarly book.. Now, of course, in your writings, you do not refer to it as Chaitin’s number. You refer to it as a capital Omega (Ώ) At Wikipedia, they call it Chaitin’s constant. Which one is correct, Chaitin’s number or Chaitin’s constant?

Note: “A constant in math is a fixed value. It may be a number on its own or a letter that stands for a fixed number in an equation.” – Reference.com It could be pi (π) or it could be the Golden Ratio in art. Some things may vary but a constant doesn’t change its relationship with other values.

Omega (Ώ) is the last capital (upper case) letter in the Greek alphabet. The small (lower case) letter is omicron (ώ)

Gregory Chaitin: It’s a little worse than that…

Robert J. Marks: It’s worse than that? Okay…

Gregory Chaitin: Because you see there isn’t one halting probability Omega. It depends on the computer programming language.

Robert J. Marks: Exactly. So Chaitin’s number varies in accordance to the computer program you’re using. Therefore calling it a constant doesn’t seem to be appropriate.

Gregory Chaitin (pictured): No. But its bizarre or fascinating properties don’t vary as long as the computer programming language you pick is a kind of a Universal Turing machine, which allows very concise programs — a general purpose computer, which allows the most possible concise programs.

You have to be a little careful what programming language you use but there are infinite numbers of programming languages which will give you a bonafide halting probability with Omega, with all the madness in it or all the fun in it.

Anyway, this is a quibble I think. In fact, in my books, I actually settled the programming language. I use a version of LISP to write an interpreter for the programming that I want to base the theory on. Once you do this, it’s a definite number with a definite numerical value that is maximally unknowable.

By the way, in my first paper, I used a lower case Omega, omicron (ώ). Anyway, Robert Salovey who at that time was working at IBM said, “Oh no, you don’t want to use lower case Omega because in set theory, lower case Omega stands for the set of natural numbers. Zero, one, two, three, four, five. Use a big Omega.”

Henceforth, I took Bob’s advice. He’s one of the best set theorists in the planet. It became capital Omega. I was sort of surprised that some people refer to it as Chaitin’s number. I’ve even seen it in lists of important mathematical constants.

Robert J. Marks: Even though it’s really not a constant, it’s a number.

Gregory Chaitin: Well it’s not a constant, right, unless you fix the programming language — which I actually do in one of my books. Also, the other constants that they give, they give them the numerical value up to a certain level of approximation. Mine is on that list simply because you can’t give… well, you can maybe get a few bits of the numerical value. But at some point it becomes unknowable.

Robert J. Marks: Has anybody computed the first few bits of Omega?

Gregory Chaitin: Yeah, my colleague Chris Calude [pictured], with another professor at the University of Auckland, in a paper called Computing a Glimpse of Randomness. They pick a different computer than I do, but it’s a good computer. It’s a universal Turing machine and it allows for the most possible concise programs.

Note: From the open access paper: “In particular, every Omega number is strongly noncomputable. The aim of this paper is to describe a procedure, that combines Java programming and mathematical proofs, to compute the exact values of the first 64 bits of a Chaitin Omega.” (2000)

The other side of the Leibniz medallion that Stephen Wolfram was kind enough to give me as a present for my 60th birthday has Omega on it. It has some bits of the Omega number that Chris Calude and his colleagues were able to calculate and prove, or correct. That’s a contradiction because in Latin, it says, the Omega number is something that you can’t calculate. But at the bottom the sum of the numerical value of one Omega number is given. That’s a nice paradox, which is always good.

Next: Chaitin’s number talks to Turing’s halting problem

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

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.

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: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