A few weeks ago one of the people that I follow on Twitter asked a question about the possible extent of human knowledge. I wrote a response, which I shared in a private forum. In order to make the response more publically available, I’ve decided to post it here, with some minor updates.

The question presents two choices: either knowledge is finite, and we will eventually have obtained all of it, or knowledge is infinite, and therefore there will always be something else for us to learn. I don’t believe that the first choice is possible even if there is finite knowledge, and so that is what we will focus on today. Perhaps at a future date we will tackle the question of infinite knowledge separately.

We can see that it is not possible for humanity to know everything there is to know because we can construct information which we can prove exists, but which we cannot construct directly. One example of such information is something called Chaitan’s Constant. Chaitan’s Constant (as specified later) is a rational number. It is a specific rational number. It is a rational number which you could write down on a sufficiently large piece of paper. Nevertheless, its specific value is not just unknown to humanity, but is fundamentally unknowable based on our understanding of mathematics. This means that humanity can never know “everything,” because there will always exist knowledge which is out of our reach.

There are some conditions which are worth noting under which this argument falls apart. If we somehow develop a method for performing infinite computation in finite time, then the problem gets murkier. With the ability to do infinite computation in finite time, you can compute Chaitan’s Constant directly. You can also do things like list out every consequence of every axiomatic system you can think of, and indeed list out every possible axiomatic system while you’re at it. Does it count to know everything if you could never think each unique thought in sequence, even if you lived a thousand lifetimes? Even if every person is collaboratively thinking every thought in sequence for the lifetime of the universe? Since our understanding of the universe does not give us any hint that operating with such infinite computations is possible, and because it somewhat exceeds the scope of what I really want to talk about (uncomputable numbers), we will disregard the possibility.

1 Theorem: Chaitin’s Constant is Unknowable

For some program encoding (like C, Perl, Lambda Calculus, Turing Machines, etc.), and for every n, there exists a value Ω_n which corresponds to the proportion of programs of length n which terminate. This value is Chaitin’s Constant for that program encoding and that length. I will shorthand that phrase as Chaitin’s Constant or Ω_n for simplicity. We will leave the particular program encoding unspecified. We can, in general, neither compute nor prove the value of any of Chaitin’s Constants, with exceptions for degenerate cases like programs of length zero, or programs which are too short to have loops represented in our chosen encoding.

1.1 Lemma: The Undecidability of the Halting Problem

It is not possible to write a program in a Turing Complete language which determines whether another arbitrary program written in a Turing Complete language eventually halts.

1.2 Proof of Lemma

Let snooper(p,i) be a function which returns true if its input program p halts on input i, and false if p runs forever on input i. We can then write a program halter() which takes as input a program p, calls snooper(p,p), and enters an infinite loop if snooper(p,p) returns true. If snooper(p,p) returns false, halter(p) returns true. Now there are two options: either halter(halter) returns true, or halter(halter) does not terminate. If halter(halter) terminates, returning true, then snooper(halter,halter) must return false, implying that halter(halter) does not terminate. If halter(halter) does not terminate, then snooper(halter,halter) must return true, implying halter(halter) does terminate. Either way, we have a contradiction that arises from the existence of the snooper program. Therefore we cannot write this snooper program; its existence leads to a contradiction.

Brief addendum: This proof is a bear to get right, and I’ve gotten minor details wrong every time I’ve presented it. Let me know if you spot an error.

1.3 Proof of our Theorem:

By Lemma 0, we cannot write a program which determines whether or not an input program halts without violating the rule that snooper-like programs cannot exist. If we know Chaitin’s constant Ω_n, then we can write such a program in the following way, assuming we are attempting to determine the halting of a program of length n :

1.

Enumerate all possible programs of length n.

2.

Execute one instruction from each program in sequence.

3.

Check your ratio of programs which have terminated over all programs.

4.

If that ratio matches Ω_n to enough decimal places that adding a single newly terminating program to the ratio would cause it to go over Ω_n, then the program we are interested in must not terminate and we can return that it does not halt. Alternately, if the program has halted, we can return that it halts.

5.

If neither of the above cases hold, then we go back to 2.

Essentially, what’s happening here is we are conducting a parallel search for all terminating programs, where we know we are done when we have reached Chaitin’s Constant. Since this is a snooper-like program (even though it would run in a truly horrendous amount of real-world computation time, even if you have a really fast computer) it cannot exist. Since its existence is predicated on our knowledge of Chaitin’s constant, we cannot mathematically prove the value of Chatin’s constant. If we can’t prove a value correct in any way, we cannot say it is correct, and therefore we cannot know it.