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 \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$c_\mathbf {S}= c_\mathbf {T}$\end{document} . We prove the following are equivalent: \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$c_\mathbf {S}\ne c_\mathbf {T}$\end{document} for some universal Turing machine, \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$r_\mathbf {S}\ne r_\mathbf {T}$\end{document} for some universal Turing machine, and T proves some Π 1 ‐sentence which S cannnot prove. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim