Mathematical Logic Quarterly 52 (4):375-403 (2006)

Abstract
We reconsider some classical natural semantics of integers in the perspective of Kolmogorov complexity. To each such semantics one can attach a simple representation of integers that we suitably effectivize in order to develop an associated Kolmogorov theory. Such effectivizations are particular instances of a general notion of “self-enumerated system” that we introduce in this paper. Our main result asserts that, with such effectivizations, Kolmogorov theory allows to quantitatively distinguish the underlying semantics. We characterize the families obtained by such effectivizations and prove that the associated Kolmogorov complexities constitute a hierarchy which coincides with that of Kolmogorov complexities defined via jump oracles and/or infinite computations . This contrasts with the well-known fact that usual Kolmogorov complexity does not depend on the chosen arithmetic representation of integers, let it be in any base n ≥ 2 or in unary. Also, in a conceptual point of view, our result can be seen as a mean to measure the degree of abstraction of these diverse semantics
Keywords recursion theory  algorithmic information theory  Kolmogorov complexity
Categories (categorize this paper)
DOI 10.1002/malq.200510040
Options
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: 70,163
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

Definability and Decision Problems in Arithmetic.Julia Robinson - 1949 - Journal of Symbolic Logic 14 (2):98-114.
Effective Operations on Partial Recursive Functions.J. Myhill & J. C. Shepherdson - 1955 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 1 (4):310-317.
Effective Operations on Partial Recursive Functions.J. Myhill & J. C. Shepherdson - 1955 - Mathematical Logic Quarterly 1 (4):310-317.
A Survey of Partial Degrees.Leonard P. Sasso - 1975 - Journal of Symbolic Logic 40 (2):130-140.
Kolmogorov Complexity for Possibly Infinite Computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.

Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Kolmogorov Complexity for Possibly Infinite Computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.
On Interpreting Chaitin's Incompleteness Theorem.Panu Raatikainen - 1998 - Journal of Philosophical Logic 27 (6):569-586.
Kolmogorov Complexity and Noncomputability.George Davie - 2002 - Mathematical Logic Quarterly 48 (4):574-581.
Effective Fractal Dimensions.Jack H. Lutz - 2005 - Mathematical Logic Quarterly 51 (1):62-72.
Complex Tilings.Bruno Durand, Leonid A. Levin & Alexander Shen - 2008 - Journal of Symbolic Logic 73 (2):593-613.
Kolmogorov Complexity and the Second Incompleteness Theorem.Makoto Kikuchi - 1997 - Archive for Mathematical Logic 36 (6):437-443.
Relative Kolmogorov Complexity and Geometry.Stephen Binns - 2011 - Journal of Symbolic Logic 76 (4):1211-1239.

Analytics

Added to PP index
2013-12-01

Total views
6 ( #1,133,362 of 2,506,511 )

Recent downloads (6 months)
1 ( #416,791 of 2,506,511 )

How can I increase my downloads?

Downloads

My notes