The axiomatic power of Kolmogorov complexity

DOI10.1016/j.apal.2014.04.009zbMath1351.03032arXiv1301.3392OpenAlexW2039720331WikidataQ57349480 ScholiaQ57349480MaRDI QIDQ2453066

Stijn Vermeeren, Laurent Bienvenu, Alexander Shen, Antoine Taveneaux, Andrei Romashchenko

Publication date: 6 June 2014

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

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

zbMATH Keywords

Kolmogorov complexityMartin-Löf randomnessprobabilistic proofs

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of proofs (03F20) Algorithmic randomness and dimension (03D32)

Related Items (2)

Approximating Kolmogorov complexity ⋮ Revisiting Chaitin's incompleteness theorem

Cites Work

• Propagation of partial randomness
• Incompleteness theorems for random reals
• Algorithmic tests and randomness with respect to a class of measures
• Kolmogorov complexity and the Recursion Theorem
• Algorithmic Randomness and Complexity
• RELATIVIZING CHAITIN'S HALTING PROBABILITY
• Enumerations of the Kolmogorov function
• ∏ 0 1 Classes and Degrees of Theories
• An introduction to Kolmogorov complexity and its applications
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The axiomatic power of Kolmogorov complexity