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$?
