Some theorems on the algorithmic approach to probability theory and information theory (1971 dissertation directed by A. N. Kolmogorov)

DOI10.1016/J.APAL.2010.09.007MaRDI QIDQ638490zbMATH OpenOpenAlexFDO

Authors Leonid A. Levin

Publication date 12 September 2011

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

Full work available at URL https://doi.org/10.1016/j.apal.2010.09.007

zbMATH Keywords

algorithmentropyinformationKolmogorov complexityrandomness

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Axioms; other general questions in probability (60A05) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Information theory (general) (94A15)

Recommendations

• scientific article; zbMATH DE number 428352
• The proof of Levin's conjecture
• scientific article; zbMATH DE number 53549
• Conditional Kolmogorov complexity and universal probability
• scientific article; zbMATH DE number 4047567

Cites work

• A formal theory of inductive inference. Part I
• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 3427323 (Why is no real title available?)
• scientific article; zbMATH DE number 3206308 (Why is no real title available?)
• scientific article; zbMATH DE number 3239528 (Why is no real title available?)
• scientific article; zbMATH DE number 3287728 (Why is no real title available?)
• scientific article; zbMATH DE number 3288611 (Why is no real title available?)
• scientific article; zbMATH DE number 3307566 (Why is no real title available?)
• scientific article; zbMATH DE number 3344568 (Why is no real title available?)
• scientific article; zbMATH DE number 3419039 (Why is no real title available?)
• scientific article; zbMATH DE number 3110190 (Why is no real title available?)
• Logical basis for information theory and probability theory
• On the Length of Programs for Computing Finite Binary Sequences
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The definition of random sequences

Cited in

(6)

• The proof of Levin's conjecture
• Putnam's diagonal argument and the impossibility of a universal learning machine
• Gacs-Kucera theorem
• scientific article; zbMATH DE number 4047567 (Why is no real title available?)
• Strict process machine complexity
• Kolmogorov complexity in the USSR (1975--1982): isolation and its end

This page was built for publication: Some theorems on the algorithmic approach to probability theory and information theory (1971 dissertation directed by A. N. Kolmogorov)

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