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 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 c_S = c_T. We prove the following are equivalent: c_S ≠ c_T for some universal Turing machine, r_S ≠ r_T for some universal Turing machine, and T proves some Π_1 -sentence which S cannnot prove.