inductive inference, fast computations, Kolmogorov, Occam

[juergen@idsia.ch]

We generalize Kolmogorov complexity and study the fastest way of computing
all computable objects, with consequences for inductive inference, Occam's 
razor, and the big picture. This might be of interest to machine learners, 
theoretical computer scientists, mathematicians, physicists, and 
philosophers. All comments are welcome.

Algorithmic Theories of Everything
Juergen Schmidhuber                      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, one reflecting the most compact constructive
descriptions, the other the fastest way of computing everything. The
former derives from generalizations of traditional computability,
Solomonoff's algorithmic probability, Kolmogorov complexity, and objects
more random than Chaitin's "number of wisdom" Omega, the latter from
Levin's universal search 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 both Ps 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, and philosophy, predicting that whatever seems random
(e.g., beta decay) is not, but in fact is computed by a short and fast
algorithm which will probably halt before our universe is many times
older than it is now.

------------------------------------------------------------------------

TR IDSIA-20-00, Version 2.0, 20 Dec 2000; 10 theorems, 50 pages, 100 refs
(minor revision of 1.0, Nov 2000, http://arXiv.org/abs/quant-ph/0011122)

ftp://ftp.idsia.ch/pub/juergen/toesv2.ps.gz   (gzipped postscript, 156K)
ftp://ftp.idsia.ch/pub/juergen/toesv2.ps      (postscript, 515K)
ftp://ftp.idsia.ch/pub/juergen/toesv2.tex.gz  (gzipped latex, 52K)
ftp://ftp.idsia.ch/pub/juergen/toesv2.tex     (latex, 155K)
ftp://ftp.idsia.ch/pub/juergen/toesv2.dvi.gz  (gzipped dvi, 91K)
ftp://ftp.idsia.ch/pub/juergen/toesv2.dvi     (dvi, 244K)
ftp://ftp.idsia.ch/pub/juergen/toesv2.pdf.gz  (gzipped pdf, 395K)
ftp://ftp.idsia.ch/pub/juergen/toesv2.pdf     (pdf, 539K)
http://www.idsia.ch/~juergen/onlinepub.html   (various formats)

PS: I am also seeking two new postdocs, please see the announcement in
http://www.idsia.ch/~juergen/postdocs2001.html