On Characteristic Constants of Theories Defined by Kolmogorov Complexity

摘要

Chaitin discovered that for each formal system T, there exists a constant c such that no sentence of the form K(x) > c is provable in T, where K(x) is the Kolmogorov complexity of x. We call the minimum such c the Chaitin characteristic constant of T, or c_T. There have been discussions about whether it represents the information content or strength of T. Raatikainen tried to reveal the true source of c_T, stating that it is determined by the smallest index of Turing machine which does not halt but we cannot prove this fact in T. We call the index the Raatikainen characteristic constant of T, denoted by r_T. We show that r-T does not necessarily coincide with c_T; for two arithmetical theories T, T' with a II_1-sentence provable in T' but not in T, there is an enumeration of the Turing machines such that r_T < r_(T') and c_T = c_(T') .