Premium
Kolmogorov complexity and characteristic constants of formal theories of arithmetic
Author(s) -
Ibuka Shingo,
Kikuchi Makoto,
Kikyo Hirotaka
Publication year - 2011
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.201010017
Subject(s) - turing machine , kolmogorov complexity , mathematics , turing , sentence , combinatorics , discrete mathematics , computer science , algorithm , artificial intelligence , computation , programming language
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