Kolmogorov complexity and characteristic constants of formal theories of arithmetic
Shingo Ibuka, Makoto Kikuchi, Hirotaka Kikyo · Mathematical logic quarterly · 2011
We investigate two constants cT and rT, 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 cT 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} e c_\mathbf {T}$\end{document} for some universal Turing machine, \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$r_\mathbf {S} e 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