Mind Matters Natural and Artificial Intelligence News and Analysis
emily-morter-188019-unsplash
Neon light question mark in dark tunnel
Photo by Emily Morter on Unsplash

Things Exist That Are Unknowable

A tutorial on Chaitin's number
Share
Facebook
Twitter
LinkedIn
Flipboard
Print
Email

Many limitations on the ability of AI are proved in the sometimes surreal mathematical world of algorithmic information theory. One of the most breathtaking results from this field is Chaitin’s number.

Chaitin’s number is an intellectually stunning piece of mathematics, ranking with Cantor’s model of the infinite and Shannon’s theory of information in terms of mind-bending brilliance.

The number exists. If you write programs in C++, Python, or Matlab, your computer language has a Chaitin number. It’s a feature of your computer programming language. But we can prove that even though Chaitin’s number exists, we can also prove it is unknowable.

The mathematically provable idea that something exists but is unknowable has clear philosophical and theological implications.

Here is why Chaitin’s number is mind-blowing: There are many problems in mathematics that can be disproved by one counterexample. Consider the theorem that all skunks are black and white. Show me a pink skunk and the theorem is disproved. Chaitin’s number—one number—can be used to prove or disprove almost every known math conjecture that can be disproven by a single counterexample.

Before explaining Chaitin’s number, I must provide some background on the Turing Halting Problem and some still unsolved problems in math. These ideas will be dovetailed into an explanation of the amazing properties of Chaitin’s number via an understandable parallel example from tax collecting. No math other than addition and subtraction is used. Nevertheless, this is not light reading for the uninitiated. Prepare to ruminate.

Unsolved Problems

Many unsolved problems in mathematics can be likewise disproved by a single counterexample. They include Goldbach’s Conjecture, the Riemann Hypothesis, the Collatz Conjecture, Carmichael’s Totient Function Conjecture, the Erdős–Straus Conjecture, the Erdős–Moser Equation conjecture and Gilbreath’s Conjecture. Large monetary prizes are offered for a solution to some of them. Each of them has an entry in Wikipedia but their specifics are not important for our current discussion of Chaitin’s number.

It is an astonishing fact that, given a lot of computing time and power, any list of problems that can be disproven by a single counterexample could be proved or disproved if we knew Chaitin’s number to finite precision. Think of it. A list of the most perplexing math problems not yet solved by the world’s top mathematicians can be answered with one single number. And not only does Chaitin’s number exist, we know it lies between zero and one.

To Halt or Not to Halt

Knowing Chaitin’s number relates to the Turing Halting Problem.

The Turing Halting Problem concludes that we cannot write a computer program to analyze an arbitrary computer program Z to determine whether program Z will stop (halt) at some time or run forever. A key word is here “arbitrary.” There are obvious cases where programs must stop or run forever. If the first line in a computer program is “STOP,” we know that the program will halt. If the computer program is “PRINT 1 then REPEAT,” the program will run forever, printing a never-ending sequence of 1’s. It never halts.

Alan Turing proved in 19371 that the Turing Halting Problem was noncomputable and thus could never be implemented on a computer. Therefore, the Turing Halting Oracle that announces whether an arbitrary computer program will halt or run forever doesn’t exist.

Will Turing’s Stoplight be Red or Green for Goldbach?

There is a relationship between the Turing Halting Problem and unsolved math problems. We’ll illustrate that with an unsolved problem from 1742 called Goldbach’s Conjecture.

Christian Goldbach observed that every positive even number he looked at could be expressed as the sum of two primes. Primes are the curious set of numbers that can only be divided by themselves and one. The first ten prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29 but they go on forever.

Let’s check Goldbach’s conjecture for a few examples. Even number 36 is the sum of 17 and 19, both of which are primes. And even number 82 is the sum of 79 and 3, both of which are primes. The conjecture also holds for really big numbers. The even number 911,111,111,344 is equal to the sum of the two primes: 911,111,111,243 and 101.

Goldbach’s conjecture has been positively tested for all even numbers up to a billion billion. But that does not prove the conjecture. There are still a lot of even numbers to check—all the way to infinity. To disprove Goldbach’s conjecture, all we need to do is identify a numerical equivalent of a pink skunk—a single even number that is not the sum of two primes.

Enter the Turing Halting Oracle. A short Goldbach computer program is written to go through the even integers one at a time in ascending order. If an even integer is the sum of two primes, the next largest even number is formed by adding two. This larger number is checked and if it is the sum of a couple of primes, two is added, and so on. The program keeps looping in its search. Inside the search loop, we give the program the following escape rule: If an even number is reached that is not the sum of two primes, the program is ordered to exit the loop and print “I HAVE FOUND A COUNTEREXAMPLE. GOLDBACH’S CONJECTURE IS WRONG!” And then the program stops.

We don’t even need to run the Goldbach program if we have a Turing Halting Oracle. We simply feed our Goldbach computer program into the Turing Halting Oracle. If the Oracle says the Goldbach program stops, then the Goldbach’s conjecture has been proven wrong. A counterexample will be found and the program will stop. If the Oracle announces that the program runs forever, then Goldbach’s conjecture is true. No counterexample will ever be found and the Goldbach program will loop forever looking for one.

The Taxman’s Deduction

To understand Chaitin’s number, consider the following tax collection problem. A man gives Beggar Bob $32 with the instructions that he should either keep it all or divide it in two and give each half to two different people. Everybody who receives money from Beggar Bob is instructed to do the same thing: keep the money or divide it in half and give each half to two different people. Beggar Bob takes the money and starts the giveaway. After all the sharing is done, the money ends up in the following hands:

$8 Iwan

$8 Austin

$4 Jonathan

$4 Charlie

$4 Angelique

$2 Pedro

$1 Winston

$1 Gordon

The sum total of the distributed money adds up to the $32 originally given to Beggar Bob. The taxman’s job is to collect taxes on all of the $32 according to who has what. He happens to know that tax has been paid on $19 of the $32 but doesn’t know who paid what. The $19, we will see, is an analogy to Chaitin’s number. We’ll call $19 the Tax Number.

To flush out the tax cheats, the taxman calls on his assistant to bring him individual records of tax payments. The assistant brings the taxman documents showing that Iwan ($8), Charlie ($4) and Pedro ($2) have all paid their taxes. This adds up to only $14 of the $19 Tax Number paid in taxes. The accounting is $5 short. Some of the other receipts for paid taxes are missing. Where are they? The taxman’s assistant says that they are at the main office but will be delivered soon.

Is there anything the taxman can deduce with the limited information he currently has? After eliminating those who have paid from the list of suspected tax cheats, the following people are left on the list.

Iwan

$8 Austin

$4 Jonathan

Charlie

$4 Angelique

Pedro

$1 Winston

$1 Gordon

There is $5 unaccounted for. The taxman immediately sees that Austin has not paid his taxes. How? Austin has $8 but only $5 is unaccounted for. If Austin had paid his taxes, the Tax Number would be exceeded by the total tax paid. So the taxman confidently puts a lien on Austin’s house. Austin has not paid his taxes and the taxman’s proof will stand up in court even with incomplete information.

The taxman’s assistant comes running into the office with more news just received. Angelique ($4) we now know has paid her taxes. So with the $16 already accounted for, we have identified the source of just $18 (=$14+$4) of the known Tax Number of $19. We’re still one dollar short.

With this new information, the taxman immediately knows that Jonathan at $4 has not paid his taxes. If he had, the Tax Number would be exceeded. With no hesitation, the taxman garnishes Jonathan’s wages.

Both of the two $1 holders, Winston and Gordon, have as of yet unknown status. We’ll only know who the tax cheat is when more information comes in from the main office.

Chaitin’s Number

In the taxman example, here’s the takeaway: Not all of the taxpayer information is needed to definitely identify a tax cheater. The key is knowing the Tax Number. As records come in, the Tax Number can’t be exceeded. If a suspect’s dollar amount added to the known taxes figure exceeds the Tax Number, the suspect is guilty. They have paid no taxes. If the sum does not exceed the Tax Number, then there is not enough evidence to announce guilt or innocence. More information is needed from the main office.

Here’s how Chaitin’s number relates to the taxman. Fundamentally, a computer program is a string of ones and zeros. Instead of starting with $32, computer programs at the machine level in binary start out with a value of just one unit. In the first giveaway, the initial one unit splits into values of ½ corresponding to a bit of either 0 or 1. The next giveaway bifurcates into one of the following: 00, 01, 10, or 11. Each is assigned a value of ¼. Each subsequent split corresponds to adding a new bit2 and each split decreases the value of a program by ½. The splitting continues until a program is complete in a distribution branch.3 The splitting, or in the case of the tax problem, the sharing, then stops for that distribution branch of the tree. Distribution and splitting continue in other branches and programs can get quite long. Long programs have low associated values.

Continuing the value splitting will eventually build a tree on which all complete computer programs live. Just as all of the dollars in the tax problem add to $32, all of the values in the computer program tree will not exceed the initial value of one unit. This is called Kraft’s Inequality.4

In the set of all computer programs in the tree, we don’t know which programs will halt or loop forever. The Turing Halting Oracle is applied to every program. The sum of the values of all complete programs that halt is Chaitin’s number. We didn’t know the identities of individual taxpayers, but we did know the sum value of the taxes paid. Similarly, we don’t know the individual values of all programs that halt, but we do know the sum of the values of all the halting programs. This number is Chaitin’s number. Just as the sum of revenue can’t exceed the Tax Number, the sum of the values of any subset of computer programs that halt cannot exceed Chaitin’s number.

Notice that the Goldbach program, a complete program, lives somewhere on the tree of all computer programs. It has a certain value in accordance to its program length in bits.

Like the Goldbach program, we now write corresponding computer programs for the Collatz Conjecture, Carmichael’s Totient Function Conjecture, the Erdős–Straus Conjecture, the Erdős–Moser Equation conjecture, Gilbreath’s Conjecture, etc. These programs also live on the tree of all computer programs, along with the Goldbach computer program. If a program for any conjecture is run and halts, the conjecture is proved false. If a program loops forever, the conjecture is true. No counterexamples are to be found in this case.

We determined the identities of some who didn’t pay their taxes by knowing the identities of others who did pay their taxes and the Tax Number. We can likewise determine which programs will loop forever by knowing only some of the computer programs that halt if we know Chaitin’s number. By running and adding the value of enough programs that do halt, we can find all of the conjecture programs that don’t halt and are therefore true. Doing so allows us to determine which conjectures are true and which are not. We submit our results to all those who offer cash prizes for solution of specific conjectures, collect, and retire to a resort in the hills of West Virginia.

Here’s the bottom line: By knowing Chaitin’s number, a single number between zero and one, we can prove or disprove all conjectures that can be disproved with a single counterexample by observing enough programs that halt.

Chaitin’s number is appropriately called “mystical and magical” by the leading text in information theory.5

Back to Earth

Here are some clarifying observations about Chaitin’s number.

First, Chaitin’s number is irrational so it goes on forever with no repeating pattern. But to apply it to a given list of conjectures, Chaitin’s number needs to be known to only finite precision. For any list of conjectures, the precision needed is determined by the longest computer program on the list of conjectures we are trying to resolve.

Second, knowing Chaitin’s number involves a cumulative sum of values obtained by a Turing Halting Oracle. The Turing Halting Oracle is noncomputable. Consequently, Chaitin’s number is unknowable.

Thirdly and sadly, the application of Chaitin’s number would be an ominous task even if we knew it. Running all complete computer programs less than a given length is an insurmountable undertaking even for the fastest parallel computers. And some programs can take eons to run before they halt. The extreme times required for certain programs to run explode into the unbelievably enormous busy beaver numbers of Algorithmic Information Theory. So the actual use of a known Chaitin’s number to prove or disprove anything looks extremely doubtful.

Learning More

To learn more about the fascinating world of Algorithmic Information Theory, I would recommend, Introduction to Evolutionary Information Theory,6 which I coauthored with William A. Dembski, and Winston Ewert. The books of Gregory Chaitin, the source of Chaitin’s number, are highly readable for the average nerd.7 Included in the list of Chaitin’s books is one titled The Unknowable.

Gregory Chaitin is credited with Andrey Kolmogorov and Ray Solomonoff as independently founding the field of Algorithmic Information Theory. Algorithmic Information Theory is also referred to as Kolmogorov-Chaitin-Solomonoff, or KCS, information theory.8 Impressively, Chaitin formulated the basics of the theory while a senior in high school in the Bronx and published his initial contributions in journal papers while still a teenager.

—– 

1 Turing, Alan Mathison. “On computable numbers, with an application to the Entscheidungsproblem.” Proceedings of the London mathematical society 2, no. 1 (1937): 230-265.

2 Some will see that the value of a program n bits long will have a value of 0.5 raised to the nth power.

3 Technically, this requires using a prefix-free (self-delimiting) program. Any computer language can be translated to such a method of coding.

4 Marks, Robert J., William A. Dembski, and Winston Ewert. Introduction to Evolutionary Informatics. 2017.

5 Cover, Thomas M., and Joy A. Thomas. Elements of information theory. John Wiley & Sons, 2012.

6 Marks, op.cit.

7 Chaitin GJ (1987) Algorithmic Information Theory (Cambridge Tracts in Theoretical Computer Science). Cambridge University Press (Cambridge).

Chaitin GJ (2002) The Limits of Mathematics: A course on Information Theory and the Limits of Formal Reasoning. Springer (New York).

Chaitin GJ (1999) The Unknowable. Springer (New York).

Chaitin GJ (2001) Exploring Randomness. Springer (New York).

Chaitin GJ (2002) Conversations with a Mathematician: Math, Art, Science and the Limits of Reason. Springer (New York).

Chaitin GJ (2006) Meta Math! The Quest for Omega. Vintage (New York).

Chaitin GJ (2007) Thinking About Gödel and Turing: Essays on Complexity, 1970-2007. World Scientific (Singapore).

8 Marks, op.cit.


Things Exist That Are Unknowable