Gacs-Kucera theorem

DOI10.1016/J.TCS.2022.06.040MaRDI QIDQ2166747zbMATH OpenOpenAlexWikidataFDO

Authors Leonid A. Levin

Publication date 25 August 2022

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

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

zbMATH Keywords

complexityrandomnessreducibility

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• The Kučera-Gács theorem revisited by Levin
• On a theorem of gács
• Limits of the Kučera–Gács Coding Method
• On the construction of effectively random sets
• Logical Approaches to Computational Barriers

Cites work

• Compression of Data Streams Down to Their Information Content
• Every sequence is reducible to a random one
• scientific article; zbMATH DE number 4008384 (Why is no real title available?)
• scientific article; zbMATH DE number 3557755 (Why is no real title available?)
• Some theorems on the algorithmic approach to probability theory and information theory (1971 dissertation directed by A. N. Kolmogorov)
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS

Cited in

(2)

• The Kučera-Gács theorem revisited by Levin
• Limits of the Kučera–Gács Coding Method

This page was built for publication: Gacs-Kucera theorem

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