Inductive reasoning and Kolmogorov complexity

DOI10.1016/0022-0000(92)90026-FzbMath0755.68079MaRDI QIDQ1190991

Ming Li, Paul M. B. Vitányi

Publication date: 27 September 1992

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

Kolmogorov complexityinductive inference

Mathematics Subject Classification ID

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

Related Items

Kolmogorov's Last Discovery? (Kolmogorov and Algorithmic Statistics), Unscrambling the quantum omelette, Compressibility, laws of nature, initial conditions and complexity, New error bounds for Solomonoff prediction, Applying MDL to learn best model granularity, Bayesian predictiveness, exchangeability and sufficientness in bacterial taxonomy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Comparison of identification criteria for machine inductive inference
• A universal prior for integers and estimation by minimum description length
• Inferring decision trees using the minimum description length principle
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Papers on probability, statistics and statistical physics. Ed. by R. D. Rosenkrantz.
• Maximum entropy as a special case of the minimum description length criterion (Corresp.)
• A theory of the learnable
• Combinatorial foundations of information theory and the calculus of probabilities
• Computational limitations on learning from examples
• Learning Simple Concepts under Simple Distributions
• A Theory of Program Size Formally Identical to Information Theory
• Complexity of automaton identification from given data
• Complexity-based induction systems: Comparisons and convergence theorems
• Prior Probabilities
• 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
• Language identification in the limit
• A formal theory of inductive inference. Part II