1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Shouldn't the additional axiom be something like: "$\pi$ is a TM that represents an unbounded monotonic function that is a lower bound of the Kolmogorov complexity on a co-finite subset of its domain" ? Or is that overkill? $\endgroup$ – Jori Apr 26 '20 at 12:45
  • $\begingroup$ Why does $S$ prove every $\Sigma_1$ fact? $\endgroup$ – Jori Apr 26 '20 at 12:46
  • $\begingroup$ @Jori "... Or is that overkill?" Yes, it's overkill (except for the bit about a cofinite subset of the domain; I just don't know what that's doing). "Why does $S$ prove every $\Sigma_1$ fact?" Basically, because $\Sigma_1$ facts - if true - are verified by concrete calculations, which $S$ can perform. (This is called "$\Sigma_1$-completeness.") In the context of Godel's incompleteness theorem, this manifests in the bit where we argue that if our theory proves something then it proves that it proves that thing (that is, "proves" is $\Sigma_1$). $\endgroup$ – Noah Schweber Apr 26 '20 at 17:01
  • $\begingroup$ This is part of the background assumption that $S$ is "appropriate" - it's the "contains enough arithmetic" bit of "consistent, computably axiomatizable, and contains enough arithmetic." The discussion here might be relevant. $\endgroup$ – Noah Schweber Apr 26 '20 at 17:04
  • $\begingroup$ Oh yes, I see. You just need to say that $\pi$ is unbounded (as formalized within $S$) to get the contradiction from Chaitin's theorem? So then this hinges on seeing why your $S'$ is an appropriate system of arithmetic. Why is that (or is it obvious)? $\endgroup$ – Jori Apr 26 '20 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.