It seems to me the recent discussion on universal Turing machines
(UTMs) versus mathematics in general occasionally suffers from certain
misunderstandings.
Schmidhuber's UTM theory of everything [1] and Tegmark's theory of
everything based on all self-consistent mathematical structures [2] are
related as follows. It is well-known that for any set of mathematical
axioms there is a program that lists all provable theorems in order
of the lengths of their proofs encoded as bitstrings. Since the UTM
that computes all bitstrings essentially outputs all these proofs for
all possible sets of axioms, Tegmark's approach [2] is encompassed by the
UTM approach [1]. In UTM speak: there is no computable universe that
simultaneously satisfies some computable criterion and its negation.
On the other hand, there are many formal axiomatic systems powerful enough
to encode all computations of all possible UTMs, such as standard number
theory. Hence Tegmark's view [2] also encompasses the UTM approach [1].
The UTM approach, however, offers several conceptual advantages: (1) It
directly connects to algorithmic and information-theoretic complexity
issues traditionally ignored in pure mathematics, and imposes natural
complexity-based orderings on the possible universes and subsets thereof.
(2) It taps into a rich source of theoretical work on computable
probability distributions relevant for establishing priors on possible
universes. Such priors are needed for making probabilistic predictions
concerning our own particular universe. For instance, Tegmark's statement
"... all mathematical structures are a priori given equal statistical
weight" [2] differs from the natural complexity-based weighting used
in [1], which builds on the "optimal" UTM-based "universal prior" or
Solomonoff-Levin distribution U.
The universal prior U assigns to a bitstring s the probability of
successively guessing all bits of a self-delimiting program that computes
s (individual bits are guessed whenever the UTM's input scanning head
shifts right). So we need to sum over all programs computing the same
universe. U is "optimal" or "universal" in the sense that it dominates
all other discrete enumerable semimeasures: under U the probability
of any computable object is at least as large (save for a constant
that does not depend on the object) as under any alternative discrete
enumerable semimeasure. The particular choice of UTM does not matter
due to the invariance theorem.
The prior U suggests: you are in the simplest universe compatible with
your existence. The conditional probability of some universe, given
yourself, is high if that universe is computable by a short algorithm. To
use the example in [1], a universe in which lambs start attacking lions
seems less probable than the present one, because apparently it requires
more information than conveyed by the few physical laws causing "normal"
animal evolution. Similarly for "flying rabbits".
The main motivation of the UTM theory of everything is Occam's razor:
given several explanations of the data, choose the simplest one - the one
requiring the least amount of information. Currently the UTM theory is
the simplest one compatible with everything we know. One may believe in
it until (a) there is evidence against it, e.g., someone shows that our
own universe won't run without all the real numbers, most of which are not
computable, or (b) someone comes up with an even simpler explanation of
everything. Note, however, that the UTM theory does encompass everything
we will ever be able to describe formally. Non-computable stuff is simply
beyond description.
[1] J.Schmidhuber. A computer scientist's view of life, the universe, and
everything. In C.Freksa, M.Jantzen, and R.Valk, editors, Foundations of
Computer Science: Theory, Cognition, Applications, volume 1337, pages
201-208. Lecture Notes in Computer Science, Springer, Berlin, 1997.
[2] M. Tegmark. Is "the theory of everything" merely the ultimate ensemble
theory? Annals of Physics, 270:1-51, 1998.
Juergen
_________________________________________________
PD Dr. Dr. habil. Juergen Schmidhuber, director
IDSIA, Corso Elvezia 36, 6900-Lugano, Switzerland
home +41 91 9212778 office +41 91 911 98 36
juergen.domain.name.hidden
http://www.idsia.ch/~juergen
Received on Thu Oct 21 1999 - 01:46:28 PDT