HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT

DOI10.1142/S0129054102001291zbMath1066.68058WikidataQ55870889 ScholiaQ55870889MaRDI QIDQ3021972

Jürgen Schmidhuber

Publication date: 22 June 2005

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

computability in the limit; computable universes; cumulatively enumerable measures; generalized algorithmic probability; generalized Kolmogorov complexity hierarchy; halting probability Omega

Mathematics Subject Classification ID

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

03D30: Other degrees and reducibilities in computability and recursion theory

03D10: Turing machines and related notions

Related Items

Revising Type-2 Computation and Degrees of Discontinuity, Real computation with least discrete advice: a complexity theory of nonuniform computability with applications to effective linear algebra, On generalized computable universal priors and their convergence, Algorithmic complexity bounds on future prediction errors, Open problems in universal induction \& intelligence, A complete theory of everything (will be subjective), On semimeasures predicting Martin-Löf random sequences, On universal prediction and Bayesian confirmation, Algorithmic complexity as a criterion of unsolvability, A coding theorem for enumerable output machines, Sequential predictions based on algorithmic complexity, A Note on Blum Static Complexity Measures

Cites Work

• Unnamed Item
• A Mathematical Theory of Communication
• On relative randomness
• On the relation between descriptional complexity and algorithmic probability
• Occam's razor
• Non-stochastic infinite and finite sequences
• Process complexity and effective random tests
• Complexity-based induction systems: Comparisons and convergence theorems
• Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
• Quantum information and computation
• A Method for the Construction of Minimum-Redundancy Codes
• On the Length of Programs for Computing Finite Binary Sequences
• Trial and error predicates and the solution to a problem of Mostowski
• Limiting recursion
• The definition of random sequences
• A formal theory of inductive inference. Part I
• New error bounds for Solomonoff prediction