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

DOI10.1142/S0129054102001291zbMath1066.68058OpenAlexW2030492659WikidataQ55870889 ScholiaQ55870889MaRDI QIDQ3021972

Jürgen Schmidhuber

Publication date: 22 June 2005

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

Full work available at URL: https://doi.org/10.1142/s0129054102001291

zbMATH Keywords

computability in the limitcomputable universescumulatively enumerable measuresgeneralized algorithmic probabilitygeneralized Kolmogorov complexity hierarchyhalting probability Omega

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Other degrees and reducibilities in computability and recursion theory (03D30) Turing machines and related notions (03D10)

Related Items (12)

A Note on Blum Static Complexity Measures ⋮ 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 ⋮ 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) ⋮ Real computation with least discrete advice: a complexity theory of nonuniform computability with applications to effective linear algebra ⋮ Revising Type-2 Computation and Degrees of Discontinuity ⋮ Sequential predictions based on algorithmic complexity

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

This page was built for publication: HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT