on formally describable universes and measures

From: <juergen.domain.name.hidden>
Date: Wed, 6 Dec 2000 09:50:27 +0100

I am pleased to announce a new paper on computable universes, inductive
inference and Occam's razor. It might be of interest to theoretical
computer scientists, mathematicians, physicists, and philosophers. All
comments are welcome, in particular: corrections, suggestions for
improving readability, simplifications of proofs, references / pointers
to be added or replaced or deleted, etc.

                  ALGORITHMIC THEORIES OF EVERYTHING
 
               Juergen Schmidhuber, IDSIA, Switzerland

We make the plausible assumption that the history of our universe is
formally describable, and sampled from a formally describable probability
distribution on the possibly infinite histories. To study consequences
for observers evolving within such a universe, we generalize the concepts
of decidability, halting problem, Kolmogorov's algorithmic complexity,
and Solomonoff's algorithmic probability. We describe objects "more
random" than Chaitin's halting probability of a Turing machine, show
that there is a universal cumulatively enumerable measure (CEM) that
dominates previous measures for inductive inference, prove that any CEM
must assign low probabilities to universes without short enumerating
programs, that any describable measure must assign low probabilities
to universes without short descriptions, and several similar "Occam's
razor theorems." Then we discuss the most efficient way of computing all
universes based on Levin's optimal search algorithm, and make a natural
resource-oriented postulate: the cumulative prior probability of all
objects incomputable within time t by this optimal algorithm should
be inversely proportional to t. We derive consequences for inductive
inference, physics, and philosophy, predicting that whatever seems random
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.

---
The essential results of the paper 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 report you
may want to skip Section 1; the main results are in Sections 3, 4, 5,
6.2, 6.5. Here is a condensed outline of the technical contents.
Section 2 introduces general Turing Machines (GTMs) that can edit their
previous outputs, and enumerable output machines (EOMs) that can do this
provided the output does not decrease lexicographically.  We define:
a formally describable bitstring x has a finite, never halting program
that computes x such that each output bit is modified at most finitely
many times, that is, each finite beginning of x eventually converges
and ceases to change (Def 2.1-2.5, p 9).
Section 3 generalizes the Kolmogorov complexity of x to the case of
(possibly infinite) x describable on EOMs and GTMs.  It is shown
(Theorem 3.3, p 15) that there are x with short GTM descriptions yet
incompressible on EOMs and therefore "more random" than Chaitin's Omega,
which is incompressible only on traditional, monotone TMs. This yields
a natural TM type-specific complexity hierarchy (p 16).
Using the results above, Section 4 extends previous work on enumerable
semimeasures by Solomonoff and Levin and others. It introduces
cumulatively enumerable measures (CEMs, Def. 4.4, p 17), where the
cumulative probability of all y lexicographically greater than x is
enumerable. It is shown that there is a universal CEM that dominates all
other CEMs as well as previous enumerable measures, in the sense that it
assigns higher probability to any finite y, save for a constant factor
independent of y (Theorem 4.1, p 18).  This probability is shown to be
equivalent to the probability that an EOM whose input bits are chosen
randomly produces an output starting with y (Corollary 4.3 and Lemma
4.2., p 24).  Section 4 also features Hutter's proof that there is no
universal approximable measure (Theorem 4.2, p 20).
Section 5 establishes relations between generalized Kolmogorov complexity
and algorithmic probability. It is shown that the universal CEM assigns
a probability to each enumerable x proportional to 1/2 raised to the
power of the length of x's minimal EOM-based description, times a
small correction factor (Theorem 5.3, p. 26), and that objects with
approximable probabilities yet without very short descriptions on GTMs
are necessarily very unlikely (Theorem 5.5, p 28).  Additional suspected
links between generalized K-complexity and probability are expressed in
form of conjectures 5.1, 5.2, 5.3 (p 29).
Section 6.2 introduces the "S-describable" universes computable within
countable time, and the fastest way of computing all of them (p 31),
based on Levin's universal search algorithm. Somewhat surprisingly, this
algorithm essentially computes each computable universe as quickly as
its fastest program, without being slowed down much by the simultaneous
computation of all the other universes. Section 6.5 then derives a natural
resource-oriented prior bias: the collective probability of all objects
incomputable in phase i of the optimal algorithm is discounted by 2^-i
(Def 6.3, p 34).  Given the resulting "speed prior," Theorem 6.1 and
Corollary 6.1 show that the best way of predicting a future y from past
observations x is to minimize the Levin complexity of (x,y).
Section 7 analyzes the inference problem of observers evolving in
universes sampled from the novel algorithmic priors above, makes
appropriate predictions for our own universe, and discusses their
falsifiability. 
---
Version 1.0, 30 Nov 2000; 55 pages, 10 theorems, 71 references 
ftp://ftp.idsia.ch/pub/juergen/toes.ps.gz   (gzipped postscript, 146K)
ftp://ftp.idsia.ch/pub/juergen/toes.ps      (postscript, 481K)
ftp://ftp.idsia.ch/pub/juergen/toes.tex     (latex, 142K)
ftp://ftp.idsia.ch/pub/juergen/toes.tex.gz  (gzipped latex, 47K)
http://www.idsia.ch/~juergen/onlinepub.html (various formats)
http://arXiv.org/abs/quant-ph/0011122       (various formats)

Received on Wed Dec 06 2000 - 00:52:21 PST