Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(x) > L$ where $K(x)$ is the Kolmogorov complexity of natural number $x$ and $L$ is a sufficiently large constant. The size of $L$ depends on the theory.

Consider the following hierarchy of theories: Let the base theory be Robinson arithmetic ($Q$). Augment $Q$ with increasingly stronger axioms of polynomial bounded induction. Let $Q^*$ be the theory of theorems provable with $Q$ and any of these bounded induction axioms.

Let $L(T)$ be the least natural number such that $T\not\vdash \exists x(K(x)\geq L(T))$. In Comparing the Kolmogorov complexity of theories I asked if there was a constant upper bound for $L(Q^*)$ and all of its sub-theories. The answer was yes. In fact, it was shown that $L(T)$ is monotonic for sub-theories of $Q^*$.

One would assume this means $L(Q) \leq L(T) \leq L(Q^*)$ where $T$ is a sub-theory of $Q^*$. $L(Q^*) - L(Q)$ is a finite number and there are an infinite number of sub-theories. Does this mean an infinite number of sub-theories of $Q^*$ have the same complexity ($L(T)$)?

Another way to ask this question: Is there some point where stronger sub-theories can no longer prove the existence of numbers with larger Kolmogorov complexity than weaker sub-theories can prove. For example, can bounded induction beyond $L(Q^*)$ prove anything about the Kolmogorov complexity of numbers that can't be proven with weaker sub-theories?

  • $\begingroup$ I'm glad to see a part two. :) $\endgroup$ – Michael Wehar Feb 28 '15 at 8:42

Your Answer

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

Browse other questions tagged or ask your own question.