…if one has ten pounds of axioms and a twenty-pound theorem, then that theorem cannot be derived from those axioms.-Gregory Chaitin

Motivation:

According to Gödel’s first incompleteness theorem, in every formal system with computably enumerable theorems strong enough to contain Peano Arithmetic there are statements that are true but unprovable. In the 1970s, Chaitin discovered an incompleteness theorem that is consistent with and just as profound as Gödel’s theorem.

Chaitin’s incompleteness theorem:

Let’s suppose we have a formal system \(F\) that contains a universal theory of computation. It follows that \(F\) has a finite description so it may be described in a finite number of bits:

\begin{equation} \exists f \in \mathbb{N}, K(F) = f \end{equation}

where \(K(\cdot)\) denotes Kolmogorov Complexity.

Given that \(F\) contains arithmetic, for any proposition \(x\) provable in \(F\) we may express:

\begin{equation} K(x) \geq |x| \end{equation}

where \(\lvert x \rvert\) is the length of the binary encoding of \(x\).

Now, let’s define a natural number \(n >> f\) and perform a stochastic search until we find a decidable proposition \(x\) of length \(n\) such that:

\begin{equation} K(x) \geq n + \text{Cst} \end{equation}

Given that the search space is of size \(\sim 2^n\) and almost all binary strings are incompressible the search algorithm has converged to (3) almost surely. Moreover, we may encode \(x\) using the integer \(n\) so we have:

\begin{equation} K(x) \leq \log_2 n + f \end{equation}

and so we have also obtained a contradiction almost surely.

Discussion:

This theorem has a natural interpretation as a complexity-bound on formal systems in the sense that if a sufficiently complex mathematical proposition is true then it is not provable. We may in fact relate this to a more general observation inference.

Formal systems are living systems that must continue to grow organically if they are to remain useful and relevant to the applications of modern physics.

References:

  1. G. J. Chaitin, Information-theoretic limitations of formal systems, J. Assoc. Comput. Mach. 21 (1974); 403–424 (Reprinted in: [19], 113–128).
  2. Cristian S. Calude & Helmut Jürgensen. Is Complexity a Source of Incompleteness? 2004.
  3. Cristian S. Calude. Randomness & Complexity, from Leibniz to Chaitin. World Scientific. 2007.