TR IDSIA-20-00, Version 2.0; 20 Dec 2000, quant-ph/0011122. Download PDF. Compare the physics archive http://arXiv.org/abs/quant-ph/0011122. Sections 1-5 led to: Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit. International Journal of Foundations of Computer Science 13(4):587-612 (2002). Section 6 led to: The Speed Prior: A New Simplicity Measure Yielding Near-Optimal Computable Predictions. In J. Kivinen and R. H. Sloan, editors, Proceedings of the 15th Annual Conference on Computational Learning Theory (COLT 2002), Sydney, Australia, Lecture Notes in Artificial Intelligence, pages 216--228. Springer, 2002.
IDSIA, Galleria 2, 6928 Manno (Lugano), Switzerland
juergen@idsia.ch - http://www.idsia.ch/~ juergen
The probability distribution P from which the history of our universe is sampled represents a theory of everything or TOE. We assume P is formally describable. Since most (uncountably many) distributions are not, this imposes a strong inductive bias. We show that P(x) is small for any universe x lacking a short description, and study the spectrum of TOEs spanned by two Ps: P1 reflects the most compact constructive descriptions, P2 the fastest way of computing all computable objects. P1 requires generalizations of traditional computability, Solomonoff's algorithmic probability, and Kolmogorov complexity; it leads to describable objects more random than Chaitin's "number of wisdom" Omega. P2 derives from Levin's universal search in program space and a natural resource-oriented postulate: the cumulative prior probability of all x incomputable within time t by this optimal algorithm should be 1/t. Between P1 and P2 we find a universal cumulatively enumerable measure that dominates traditional enumerable measures; any such CEM must assign low probability to any universe lacking a short enumerating program. We derive P-specific consequences for observers evolving in computable universes, inductive reasoning, quantum physics, philosophy, and the expected duration of our universe.
Post publication note: Konrad Zuse was the first who seriously suggested the universe is being computed (on a cellular automaton). A recent journal publication derived from chapters 1-5 of the present report is described here (IJFCS 2002). A recent conference publication derived from chapter 6 of the present report is described here (COLT 2002). An earlier paper on all computable universes can be found here (1997). These papers and related ones are being discussed on Wei Dai's everything mailing list (everything-list@eskimo.com). Follow this link to the main page; or pick out messages referring to Schmidhuber's work.
10 theorems, 50 pages, 100 references, 20000 words
Keywords: formal describability, constructive mathematics, randomness, pseudorandomness, minimal description length, generalized Kolmogorov complexity, complexity hierarchy, algorithmic probability, halting probability Omega, convergence probability, semimeasures, cumulatively enumerable measures, universal priors, speed prior, universal search, inductive inference, Occam's razor, computable universes, theory of everything, collapse of the wave function, many worlds interpretation of quantum mechanics, countable vs uncountable.
Note:
This is a slightly revised version of a recent preprint
[#!Schmidhuber:00version1!#]. The essential results should be of
interest from a purely theoretical point of view independent of the
motivation through formally describable universes. To get to the
meat of the paper, skip the introduction and go immediately to
Subsection 1.1 which provides a condensed outline of the main
theorems.