TY - JOUR

T1 - Hierarchies of generalized kolmogorov complexities and nonenumerable universal measures computable in the limit

AU - Schmidhuber, Jürgen

N1 - Generated from Scopus record by KAUST IRTS on 2022-09-14

PY - 2002/12/1

Y1 - 2002/12/1

N2 - 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. © 2002 World Scientific Publishing Company.

AB - 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. © 2002 World Scientific Publishing Company.

UR - https://www.worldscientific.com/doi/abs/10.1142/S0129054102001291

UR - http://www.scopus.com/inward/record.url?scp=1642358077&partnerID=8YFLogxK

U2 - 10.1142/S0129054102001291

DO - 10.1142/S0129054102001291

M3 - Article

SN - 0129-0541

VL - 13

SP - 587

EP - 612

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

IS - 4

ER -