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$ Feb 28, 2015 at 8:42


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.