Inductive reasoning and Kolmogorov complexity
type: Item
instance of: scholarly article
title: Inductive reasoning and Kolmogorov complexity
zbMATH Open document ID: 0755.68079
DOI: 10.1016/0022-0000(92)90026-F
author: Ming Li
author: Paul M. B. Vitányi
published in: Journal of Computer and System Sciences
publication date: 1992-09-27T00:00:00Z
review text: In this comprehensive note, the authors discuss several basic senses of inductive inference and their generalization to inductive reasoning. Neither Zadeh-type fuzzy reasoning nor Peirce-type abductive reasoning is addressed there. In the process, the authors refine Ockham's Rozor and combine principles of Epicurus, Ockham and Bayes in various useful ways, e.g., in relation to the non-effective notion of Kolmogorov complexity. The main thesis of this detailed, analytical paper is that various theories, approaches, simulations, models, programs and principles of inductive reasoning can be formulated as specific computable approximations to \textit{R. J. Solomonoff's} [Inform. and Control 7, 1-22 (1964; Zbl 0258.68045)] non-effective procedures.
Mathematics Subject Classification ID: 68Q30
Mathematics Subject Classification ID: 68T15
zbMATH DE Number: 58813
zbMATH Keywords: inductive inference
zbMATH Keywords: Kolmogorov complexity
reviewed by: Albert A. Mullin
MaRDI profile type: Publication
cites work: Fast probabilistic algorithms for Hamiltonian circuits and matchings
cites work: Comparison of identification criteria for machine inductive inference
cites work: On the Length of Programs for Computing Finite Binary Sequences
cites work: A Theory of Program Size Formally Identical to Information Theory
cites work: Maximum entropy as a special case of the minimum description length criterion (Corresp.)
cites work: Q5538132
cites work: Q5595624
cites work: Language identification in the limit
cites work: Complexity of automaton identification from given data
cites work: Q4074808
cites work: Prior Probabilities
cites work: Papers on probability, statistics and statistical physics. Ed. by R. D. Rosenkrantz.
cites work: Q5726065
cites work: Q3214803
cites work: Q5681915
cites work: Combinatorial foundations of information theory and the calculus of probabilities
cites work: Q5808621
cites work: Q4070738
cites work: Learning Simple Concepts under Simple Distributions
cites work: Q4385509
cites work: Q4337021
cites work: The definition of random sequences
cites work: Q3219516
cites work: Computational limitations on learning from examples
cites work: Inferring decision trees using the minimum description length principle
cites work: A universal prior for integers and estimation by minimum description length
cites work: A formal theory of inductive inference. Part II
cites work: Complexity-based induction systems: Comparisons and convergence theorems
cites work: A theory of the learnable
cites work: THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
description: scientific article; zbMATH DE number 58813