Kolmogorov complexity and characteristic constants of formal theories of arithmetic
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 . We prove the following are equivalent: for some universal Turing machine, for some universal Turing machine, and T proves some ?1-sentence which S cannnot prove.  2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim
kolmogorov complexity characteristic constant msc (2010) 03a99 03b25