Logical operations and Kolmogorov complexity

DOI10.1016/S0304-3975(01)00035-4zbMath0982.68079WikidataQ57349827 ScholiaQ57349827MaRDI QIDQ5958286

Alexander Shen, Nikolai K. Vereshchagin

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Kolmogorov complexityrealizabilityintuitionistic logic

Mathematics Subject Classification ID

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

Related Items (10)

Mutual dimension and random sequences ⋮ Finite problems and the logic of the weak law of excluded middle ⋮ INFORMATION DISTANCE AND ITS APPLICATIONS ⋮ Who Asked Us? How the Theory of Computing Answers Questions about Analysis ⋮ Nonapproximability of the normalized information distance ⋮ Constructive logic and the Medvedev lattice ⋮ On joint conditional complexity (entropy) ⋮ Kolmogorov complexity and cryptography ⋮ Mutual Dimension ⋮ Algorithmic Fractal Dimensions in Geometric Measure Theory

Cites Work

• Unnamed Item
• Unnamed Item
• Zur Deutung der intuitionistischen Logik
• Thermodynamics of computation and information distance

This page was built for publication: Logical operations and Kolmogorov complexity