(some equations may be hard to read without knowledge of LATEX)

**JÜRGEN SCHMIDHUBER
juergen@idsia.ch - http://www.idsia.ch/~ juergen
IDSIA, Galleria 2, 6928 Manno (Lugano), Switzerland
**

**Original work: Dec 2000 (quant-ph/0011122)**

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 is the size of the shortest nonhalting program that converges to and nothing but 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 is small for any lacking a short description, that there is no universal approximable distribution, that there is a universal CEM, and that any nonenumerable CEM of is small for any lacking a short enumerating program. We briefly mention consequences for universes sampled from such priors.

**Keywords:** computability in the limit,
generalized algorithmic probability,
generalized Kolmogorov complexity hierarchy,
halting probability Omega,
cumulatively enumerable measures,
computable universes.

- Introduction and Outline
- Preliminaries
- Notation
- Turing Machines: Monotone TMs (MTMs), General TMs (GTMs), Enumerable Output Machines (EOMs)
- Infinite Computations, Convergence, Formal Describability
- Formally Describable Functions
- Weak Decidability and Convergence Problem

- Complexity of Constructive Descriptions
- Generalized Kolmogorov Complexity for EOMs and GTMs
- Expressiveness of EOMs and GTMs
- Which is the ``True'' Information Content of ?
- Relation to Conditional Complexity

- Measures and Probability Distributions
- Dominant and Universal (Semi)Measures
- A Novel Universal Cumulatively Enumerable Measure (CEM)
- Approximable and Cumulatively Enumerable Distributions
- TM-Induced Distributions and Convergence Probability
- Universal TM-Induced Measures
- Universal CEM vs EOM with Random Input

- Probability vs Descriptive Complexity

- Consequences for Physics
- Acknowledgments
- Bibliography
- About this document ...