Explaining Chaitin's Incompleteness Theorem
This blog is more or less a copy of the Wikipedia article on Chaitin's Incompleteness Theorem where I am additionally adding in my own explanations to help make sense of things. I am writing this as a means to check my understanding and share what I think is a really cool idea; that even with as little as we know of the universe we live in, we know that there will always be meaningful questions we can ask that logic alone cannot provide the answer to.
In the computer science sense of the word, "strings" are sequences of characters. Things like "abcd" or "1 and a half" or "strings are sequences of characters" are examples of strings (anything in quotes).
We know that, in the set of all possible strings, most strings are complex in the sense that they cannot be described in any significantly compressed way.
For example, the string
abababababababababababababababab
can be described in a more compressed fashion as "ab 16 times", a string with 11 characters as opposed to 32 characters required for the original representation.
However, there are also strings like
4c1j5b2p0cv4w1x8rx2y39umgw5q85s7
that are also 32 characters long, but do not have any apparent way to compress the representation of the information contained in the string. This latter string is an example of what is called a "complex string", one that cannot be compressed.
The "complexity" of a string is defined to be the minimum description length of that string in a given axiomatic system. For example, we know that the complexity of
abababababababababababababababab
In case you haven't come across the term before, an "axiomatic system" means a system based on fundamental statements we assume to be true (called the "axioms" of the system) that we can apply the rules of logic to as a means to derive new statements that are true. For example, arithmetic is based on just 9 axioms (Peano's Key Axioms) from which we can use the rules of logic to generate all of the arithmetically true statements and theorems we know today.It turns out that the fact that a specific string is complex cannot be formally proven when the complexity of the string is above a certain threshold. The precise formalization is as follows:
First, fix a particular axiomatic system S for the natural numbers. The axiomatic system has to be powerful enough so that, to certain assertions A about the complexity of strings, one can associate a formula FA in S. This association must have the following property: if FA is provable from the axioms of S, then the corresponding assertion A must be true. This "formalization" can be achieved either by an artificial encoding such as Godel numbering, or by a formalization which more clearly respects the intended interpretation of S.
Chaitin's Incompleteness Theorem: There exists a constant L (which only depends on the particular axiomatic system and the choice of description language) such that there does not exist a string for which the statement K(S) ≥ L cab be proven within the axiomatic system S.
The proof of this result is modeled on a self-referential construction used in Berry's paradox, and is a proof made by way of contradiction (BWoC).
The way BWoC proofs work may seem a little weird if you haven't seen them before
[ADD SOME ADDITIONAL EXPLANATION OF BWoC HERE]
Proof:
Assume that the theorem is not true. This directly implies that the following is true.
Assumption (X): For any integer n there exists a string for which there is a proof in S of the formula "K(S) ≥ n".
Note that Assumption (X) also tacitly assumes that the formula "K(S) ≥ n" can be formalized in S. However, this assumption is something we are free to take as a given since we know such systems exist (e.g. our number system) and can be assumed to be a subcomponent of the system S of interest.
Take it as a given that we have already gone through the process of effectively enumerating all the formal proofs in S by some procedure, meaning we have assigned a unique integer to each proof. This is to say that we can think of all of the theorems that exist as belonging to some really long list.
This may seem like a weird thing to take as a given, but a simple example of how this could be done in practice is by numbering theorems in the order in which they were/will be initially derived. Although none of us would ever see the list in its entirety, we can still infer that such a list exists in principle.
This provides us with a means to create the function called "NthProof"
function NthProof(int n)
Most of the proofs are for formulas we do not care about here, since every possible proof in the language of S is produced for some n. However, some of these proofs are for complexity formulas of the form K(s) ≥ n where s and n are constants in the language of S. For example, a proof of the form
K(4c1j5b2p0cv4w1x8rx2y39umgw5q85s7) > 31
would be one of these if it was meaningful in S.
Also take it as a given that we've already constructed the following programs: NthProofProvesComplexityFormula, ComplexityLowerBoundNthProof, and StringNthProof; defined in the following.
The function we call NthProofProvesComplexityFormula,
function NthProofProvesComplexityFormula(int n)
performs a simple check to determine whether the nth proof actually proves a complexity formula K(S) ≥ L for a specific s and L.
The function we call ComplexityLowerBoundNthProof,
The function we call ComplexityLowerBoundNthProof,
function ComplexityLowerBoundNthProof(int n)
returns L
simply returns the integer L from the proof.
And the function we call StringNthProof,
And the function we call StringNthProof,
function StringNthProof(int n)
returns s
which returns the string s from the proof.
Now, consider the following program we'll call GenerateProvablyComplexString(int n) that can be built from those functions.
function GenerateProvablyComplexString(int n)
for i = 1 to infinity, perform the following check
if NthProofProvesComplexityFormula(i) and ComplexityLowerBoundNthProof(i) ≥ n
return StringNthProof(i)
Given an input integer, n, this program examines every proof until it finds a string and a proof in the formal system S of the formula K(s) ≥ L for some L ≥ n.
The program terminates by our Assumption (X), meaning that the GenerateProvablyComplexString program itself also serves as a way of describing the string returned by it.
Now, consider the program GenerateProvablyParadoxicalString,
function GenerateProvablyParadoxicalString()
return GenerateProvablyComplexString(L)
that will generate a string whose maximal complexity is no greater than L.
Let C be the description length of this program and note that the description length of a fixed number, L, is log2(L). This means that the total description length of the string returned by this program when n = L can be no greater than C + log2(L), again because the program itself serves as a description for the string.
Note that C is a fixed quantity; it is simply the total description length of all the programs used to return any provably complex string plus the minor addition it takes to describe the GenerateProvablyParadoxicalString function.
Given C, simple arithmetic shows us how to find an integer L such that C+ log2(L) < L.
The program GenerateProvablyParadoxicalString outputs a string s for which there exists an L such that "K(s) ≥ L" is actually a theorem that is true in S, but for which we have constructed an explicit counter example which demonstrates that the fact is "K(s) < L".
This is a contradiction, meaning either that S is inconsistent (contains statements that are provably both true and false) or our Assumption (X) is incorrect.
If we have faith that our system S is consistent, then we have to conclude that Assumption (X) is incorrect. If Assumption (X) is incorrect, then Chaitin's Incompleteness Theorem is correct.