Kolmogorov complexity and characteristic constants of formal theories of arithmetic

We investigate two constants c _T and r _T , introduced by Chaitin and Raatikainen respectively, defined for each recursively axiomatizable consistent theory T and universal Turing machine used to determine Kolmogorov complexity. Raatikainen argued that c _T does not represent the complexity of T and found that for two theories S and T , one can always find a universal Turing machine such that $c_\mathbf {S}= c_\mathbf {T}$. We prove the following are equivalent: $c_\mathbf {S}\ne c_\mathbf {T}$ for some universal Turing machine, $r_\mathbf {S}\ne r_\mathbf {T}$ for some universal Turing machine, and T proves some Π₁‐sentence which S cannnot prove. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim