Mathematical Logic Quarterly 57 (5):470-473 (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 equation image. We prove the following are equivalent: equation image for some universal Turing machine, equation image for some universal Turing machine, and T proves some Π1-sentence which S cannnot prove. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim
Keywords 03B25  Characteristic constant  Kolmogorov complexity  MSC (2010) 03A99
Categories (categorize this paper)
DOI 10.1002/malq.201010017
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,172
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

On Interpreting Chaitin's Incompleteness Theorem.Panu Raatikainen - 1998 - Journal of Philosophical Logic 27 (6):569-586.
Algorithmic Information Theory.Michiel van Lambalgen - 1989 - Journal of Symbolic Logic 54 (4):1389-1400.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles


Added to PP index

Total views
9 ( #954,194 of 2,517,884 )

Recent downloads (6 months)
1 ( #409,482 of 2,517,884 )

How can I increase my downloads?


My notes