COMPLEXITY OF COMPLEXITY AND STRINGS WITH MAXIMAL PLAIN AND PREFIX KOLMOGOROV COMPLEXITY

DOI10.1017/jsl.2014.15zbMath1338.68126arXiv1202.6668OpenAlexW2964111135WikidataQ57349447 ScholiaQ57349447MaRDI QIDQ2921012

Bruno Bauwens, Alexander Shen

Publication date: 30 September 2014

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

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

zbMATH Keywords

Kolmogorov complexity of Kolmogorov complexityplain and prefix Kolmogorov complexityplain and prefix randomness deficiency

Mathematics Subject Classification ID

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

Related Items (6)

The Normalized Algorithmic Information Distance Can Not Be Approximated ⋮ Relating and contrasting plain and prefix Kolmogorov complexity ⋮ Enumerations including laconic enumerators ⋮ Proofs of conservation inequalities for Levin's notion of mutual information of 1974 ⋮ Short lists with short programs in short time ⋮ Searching for shortest and least programs

Cites Work

• Algorithmic Randomness and Complexity
• An introduction to Kolmogorov complexity and its applications

This page was built for publication: COMPLEXITY OF COMPLEXITY AND STRINGS WITH MAXIMAL PLAIN AND PREFIX KOLMOGOROV COMPLEXITY