Kolmogorov complexity and set theoretical representations of integers

DOI10.1002/MALQ.200510040MaRDI QIDQ5485491zbMATH OpenOpenAlexFDO

Authors Serge Grigorieff, Marie C. Ferbus-Zanda

Publication date 30 August 2006

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0801.0353

zbMATH Keywords

Kolmogorov complexity

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Semantics in the theory of computing (68Q55)

Abstract: We reconsider some classical natural semantics of integers (namely iterators of functions, cardinals of sets, index of equivalence relations), 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 (up to a constant) on the chosen arithmetic representation of integers, let it be in any base unary, binary et so on. 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.

Recommendations

• The Kolmogorov complexity of real numbers.
• Publication:4934359
• The Kolmogorov expression complexity of logics
• Kolmogorov Complexity Theory over the Reals
• Kolmogorov complexities \(K_{\max}\), \(K_{\min}\) on computable partially ordered sets

Cited in

(6)

• Recursion and topology on \(2^{\leq\omega}\) for possibly infinite computations
• scientific article; zbMATH DE number 1390092 (Why is no real title available?)
• Kolmogorov complexity in perspective. I: Information theory and randomness
• New Computational Paradigms
• Kolmogorov complexity conditional to large integers
• Kolmogorov complexities \(K_{\max}\), \(K_{\min}\) on computable partially ordered sets

This page was built for publication: Kolmogorov complexity and set theoretical representations of integers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5485491)