- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Juergen Schmidhuber <juergen.domain.name.hidden>

Date: Thu, 21 Oct 1999 10:43:20 +0200

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

Date: Thu, 21 Oct 1999 10:43:20 +0200

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

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:06 PST
*