A consequence of Chaitin's incompleteness theorem

138 Views Asked by At

According to Wikipedia due to Chaitin's incompleteness theorem, the output of any program computing a lower bound of the Kolmogorov complexity cannot exceed some fixed limit, which is independent of the input string $s$.

They formulate Chaitin's incompleteness theorem as

Theorem: There exists a constant $L$ (which only depends on $S$, some axiomatization of arithmetic, and on the choice of description language) such that there does not exist a string $s$ for which the statement

K(s) ≥ L (as formalized in $S$)

can be proven within $S$

How exactly does this imply the former?

1

There are 1 best solutions below

7
On BEST ANSWER

Suppose to the contrary that such a program $\pi$ existed. Then take your favorite $S$ and add to it the sentence "$\pi$ computes lower bounds of Kolmogorov complexities." The resulting system $S'$ is again an appropriate system of arithmetic and so we can apply Chaitin's theorem to get the corresponding $L$.

But now by assumption, there is some input such that $\pi$ halts on that input and outputs something $>L$. This would yield an instance in $S'$ of a proved lower bound on Kolmogorov complexity greater than $L$, a contradiction.


This may seem rather slippery: where are we using the particular nature of $\pi$ in building $S'$? For example, suppose $\sigma$ is any program with unbounded output (say, the identity). What would happen if we considered the theory $\hat{S}=S+$"$\sigma$ computes lower bounds of Kolmogorov complexities"?

Well, the issue is that this $\hat{S}$ would be inconsistent! For some $x$ we'd have $\sigma(x)>K(x)$, and this is a $\Sigma_1$ fact (remember, $S$ proves every true $\Sigma_1$ fact). So basically we have the following:

For a program $\pi$, consider the theory $S_\pi=S+$"$\pi$ computes lower bounds on Kolmogorov complexities." Either $S_\pi$ is inconsistent, or the range of $\pi$ is bounded.