Axiomatizing Kolmogorov complexity

DOI10.1007/S00224-012-9395-2MaRDI QIDQ1946501zbMATH OpenOpenAlexFDO

Authors Antoine Taveneaux

Publication date 15 April 2013

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-012-9395-2

zbMATH Keywords

Kolmogorov complexityslow growing functions

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Towards an axiomatic system for Kolmogorov complexity
• The axiomatic power of Kolmogorov complexity
• Conditional Kolmogorov complexity and universal probability
• scientific article; zbMATH DE number 107774
• On joint conditional complexity (entropy)

Cites work

• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• Algorithmic randomness and complexity.
• On the Length of Programs for Computing Finite Binary Sequences

Cited in

(7)

• Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts
• scientific article; zbMATH DE number 1236369 (Why is no real title available?)
• The axiomatic power of Kolmogorov complexity
• scientific article; zbMATH DE number 7139948 (Why is no real title available?)
• An additivity theorem for plain Kolmogorov complexity
• Towards an axiomatic system for Kolmogorov complexity
• A note on the Kolmogorov data complexity and nonuniform logical definitions

This page was built for publication: Axiomatizing Kolmogorov complexity

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