HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT
The DOI matches its Crossref record; 4 of the 4 references it cites were found in a registry or an index.
Abstract
The traditional theory of Kolmogorov complexity and algorithmic probability focuses on monotone Turing machines with one-way write-only output tape. This naturally leads to the universal enumerable Solomonoff-Levin measure. Here we introduce more general, nonenumerable but cumulatively enumerable measures (CEMs) derived from Turing machines with lexicographically nondecreasing output and random input, and even more general approximable measures and distributions computable in the limit. We obtain a natural hierarchy of generalizations of algorithmic probability and Kolmogorov complexity, suggesting that the "true" information content of some (possibly infinite) bitstring x is the size of the shortest nonhalting program that converges to x and nothing but x on a Turing machine that can edit its previous outputs. Among other things we show that there are objects computable in the limit yet more random than Chaitin's "number of wisdom" Omega, that any approximable measure of x is small for any x lacking a short description, that there is no universal approximable distribution, that there is a universal CEM, and that any nonenumerable CEM of x is small for any x lacking a short enumerating program. We briefly mention consequences for universes sampled from such priors.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Quantum information and computation
Bennett, C. H., & DiVincenzo, D. P. (2000) · Nature · doi:10.1038/35005001 · Cited by 3,263 · cited 1×
“, [3]) and Heisenberg's uncertainty principle do not rule this out [35].”
BackgroundÜber formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
Gödel, K. (1931) · Monatshefte für Mathematik und Physik · doi:10.1007/bf01700692 · Cited by 2,395
A formal theory of inductive inference. Part I
Solomonoff, R. J. (1964) · Information and Control · doi:10.1016/s0019-9958(64)90223-2 · Cited by 1,192
Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1987) · Information Processing Letters · doi:10.1016/0020-0190(87)90114-1 · Cited by 1,054
Cited by
Formal theory of creativity, fun, and intrinsic motivation (1990–2010)
Schmidhuber, J. (2010) · IEEE Transactions on Autonomous Mental Development · doi:10.1109/tamd.2010.2056368 · Cited by 747
Self-citationDevelopmental robotics, optimal artificial curiosity, creativity, music, and the fine arts
Schmidhuber, J. (2006) · Connection Science · doi:10.1080/09540090600768658 · Cited by 268
Self-citationGödel Machines: Fully Self-referential Optimal Universal Self-improvers
Schmidhuber, J. (2007) · Cognitive Technologies · doi:10.1007/978-3-540-68677-4_7 · Cited by 110
Self-citationMindstorms in Natural Language-Based Societies of Mind
Zhuge, M., Liu, H., Faccio, F., Ashley, D. R., Csordás, R., Gopalakrishnan, A., Hamdi, A., Hammoud, H. A. A. K., Herrmann, V., Irie, K., et al. (2023) · arXiv · doi:10.48550/arxiv.2305.17066 · Cited by 24
Self-citationMindstorms in Natural Language-Based Societies of Mind
Zhuge, M., Liu, H., Faccio, F., Ashley, D. R., Csordás, R., Gopalakrishnan, A., Hamdi, A., Hammoud, H. A. A. K., Herrmann, V., Irie, K., et al. (2025) · Computational Visual Media · doi:10.26599/cvm.2025.9450460 · Cited by 24
Self-citation
Metadata
- Authors
- SCHMIDHUBER, J.
- Venue
- International Journal of Foundations of Computer Science
- Publisher
- World Scientific Pub Co Pte Lt
- Published
- 2002-08
- Volume
- 13
- Issue
- 04
- Pages
- 587-612
- ISSN
- 0129-0541 (ISSN-L)
- 1793-6373
- OpenAlex
- W2030492659
- Cited by
- 98
- References
- 4
- FWCI
- 7.21
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT. https://app.cochat.ai/papers/10.1142/s0129054102001291
- The paper
- SCHMIDHUBER, J. (2002). HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT. International Journal of Foundations of Computer Science. https://doi.org/10.1142/s0129054102001291
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.