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

Some people have suggested since the minimum value of $L$ depends on the theory, $T$, the minimum value of $L(T)$ can be used as a measure of the complexity of theory $T$. Other people have argued this is a very bad idea. At least one person has speculated the complexity of Peano arithmetic is less than $10^9$.

Assume we define $K(x)$ using n-state, 2-symbol busy beavers(BB). $K(x)=n$ where $n$ is the number of states of the smallest BB that writes exactly $x$ 1's and halts. We don't really need a strong theory to write a computer program so assume our theory, $T$, is primitive recursive arithmetic. One way to define $L(PRA)$ is to define it as the size of a computer program that can determine the truth of any statement of the form $K(n) > m$ for any positive integers $n,m$. Assume the programming language is x86 assembly. The size of the program is the size in bits of a compiled executable running on a 64-bit processor.

What is a reasonable value for $L(PRA)$? Are there any papers with upper bounds on $L(T)$ for some $T$?



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.