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

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

Date: Tue, 13 Nov 2001 12:05:22 +0100

Wei Dai wrote:

*>
*

*> On Wed, Oct 31, 2001 at 10:49:41AM +0100, Juergen Schmidhuber wrote:
*

*> > Which are the logically possible universes? Tegmark mentioned a
*

*> > somewhat
*

*> > vaguely defined set of ``self-consistent mathematical structures,''
*

*> > implying provability of some sort. The postings of Marchal also focus
*

*> > on what's provable and what's not.
*

*>
*

*> Do you understand Marchal's postings? I really have trouble making sense
*

*> of them. If you do, would you mind rephrasing his main ideas for me?
*

No, unfortunately I do not understand him. But provability does seem

important to him. Maybe someone else could post a brief and concise

summary?

*> > Is provability really relevant? Philosophers and physicists find it
*

*> > sexy for its Goedelian limits. But what does this have to do with the
*

*> > set of possible universes?
*

*>
*

*> What does it mean for a universe to be "provable"? One interpretation is
*

*> that there exists an algorithm to compute any finite time-space region of
*

*> the universe that always halts. Is that what you mean?
*

Well, any finite object x has a halting algorithm that computes it.

So which are the unprovable things? They are formal statements such as

"algorithm x will eventually compute object y." If it does then you can

prove it, otherwise in general you can never be sure. But why identify

universes with true or false statements? When I'm asking "Is provability

really relevant?" I am not really referring to "provable universes" -

I don't even know what that is supposed to be. I just mean: why should

it be important to show that a particular algorithm computes a

particular

universe? Or that a particular universe has a particular property (there

are many generally unprovable properties)? Let's compute them all -

why worry about provability?

*> > The provability discussion seems to distract from the real issue. If we
*

*> > limit ourselves to universes corresponding to traditionally provable
*

*> > theorems then we will miss out on many formally and constructively
*

*> > describable universes that are computable in the limit yet in a certain
*

*> > sense soaked with unprovability.
*

*> >
*

*> > Example: a never ending universe history h is computed by a finite
*

*> > nonhalting program p. To simulate randomness and noise etc, p invokes
*

*> > a short pseudorandom generator subroutine q which also never halts. The
*

*> > n-th pseudorandom event of history h is based on q's n-th output bit
*

*> > q(n)
*

*> > which is initialized by 0 and set to 1 as soon as the n-th statement in
*

*> > an ordered list of all possible statements of a formal axiomatic system
*

*> > is proven by a theorem prover that systematically computes all provable
*

*> > theorems. Whenever q modifies some q(n) that was already used in the
*

*> > previous computation of h, p appropriately recomputes h since the n-th
*

*> > pseudorandom event.
*

*>
*

*> Living in this universe is like living in a universe with a
*

*> halting-problem oracle, right? If you want to know whether program x
*

*> halts, you just measure the n-th pseudorandom event, where n is such that
*

*> the n-th theorem is "x halts." Yes?
*

Yes. Once the history has stabilized this will give you the correct

answer.

*> The problem with universes with halting-problem oracles (which I'll just
*

*> call oracle universes) is that either the oracle is not exploitable
*

*> (for example if no one in the universe figures out that the pseudorandom
*

*> events actually correspond to theorems) in which case the universe just
*

*> looks like an ordinary "provable" universe, or the oracle is
*

*> exploitable, in which case the outcome becomes completely unimaginable for
*

*> us. (Or is that not true? Can we imagine what would happen if an
*

*> intelligent species came across an exploitable halting-problem oracle?)
*

*>
*

*> > But why should this lack of provability matter? Ignoring this universe
*

*> > just implies loss of generality. Provability is not the issue.
*

*>
*

*> If oracle universes could exist, how significant are they? What's
*

*> the probability that we live in such a universe, and how could we try to
*

*> determine and/or exploit this fact?
*

If the computer on which the history of our universe is calculated is a

general Turing machine (as opposed to a monotone machine which cannot

edit

previous outputs), and if we make no resource assumptions such as those

embodied by the Speed Prior, then the oracle universes indeed represent

a large fraction of the probability mass of all universes. Why? Because

there are many oracle universes with very short algorithms.

How to determine whether we are in an oracle universe? In principle it

is possible, at least to the extent inductive inference is possible at

all! Just search through all oracle pseudo-random generators (PRGs) and

try to match their outputs with the apparently noisy observations. If

the observations are not really random, eventually you'll stumble across

the right PRG. It's just that you cannot prove that it is the right one,

or that its outputs have already stabilized.

What about exploitation? Once you suspect you found the PRG you can use

it

to predict the future. Unfortunately the prediction will take enormous

time to stabilize, and you never can be sure it's finished. So it's not

very practical. I prefer the additional resource assumptions reflected

by the Speed Prior. They make the oracle universes very unlikely, and

yield computable predictions.

Juergen Schmidhuber

http://www.idsia.ch/~juergen/

http://www.idsia.ch/~juergen/everything/html.html

http://www.idsia.ch/~juergen/toesv2/

Received on Tue Nov 13 2001 - 03:07:14 PST

Date: Tue, 13 Nov 2001 12:05:22 +0100

Wei Dai wrote:

No, unfortunately I do not understand him. But provability does seem

important to him. Maybe someone else could post a brief and concise

summary?

Well, any finite object x has a halting algorithm that computes it.

So which are the unprovable things? They are formal statements such as

"algorithm x will eventually compute object y." If it does then you can

prove it, otherwise in general you can never be sure. But why identify

universes with true or false statements? When I'm asking "Is provability

really relevant?" I am not really referring to "provable universes" -

I don't even know what that is supposed to be. I just mean: why should

it be important to show that a particular algorithm computes a

particular

universe? Or that a particular universe has a particular property (there

are many generally unprovable properties)? Let's compute them all -

why worry about provability?

Yes. Once the history has stabilized this will give you the correct

answer.

If the computer on which the history of our universe is calculated is a

general Turing machine (as opposed to a monotone machine which cannot

edit

previous outputs), and if we make no resource assumptions such as those

embodied by the Speed Prior, then the oracle universes indeed represent

a large fraction of the probability mass of all universes. Why? Because

there are many oracle universes with very short algorithms.

How to determine whether we are in an oracle universe? In principle it

is possible, at least to the extent inductive inference is possible at

all! Just search through all oracle pseudo-random generators (PRGs) and

try to match their outputs with the apparently noisy observations. If

the observations are not really random, eventually you'll stumble across

the right PRG. It's just that you cannot prove that it is the right one,

or that its outputs have already stabilized.

What about exploitation? Once you suspect you found the PRG you can use

it

to predict the future. Unfortunately the prediction will take enormous

time to stabilize, and you never can be sure it's finished. So it's not

very practical. I prefer the additional resource assumptions reflected

by the Speed Prior. They make the oracle universes very unlikely, and

yield computable predictions.

Juergen Schmidhuber

http://www.idsia.ch/~juergen/

http://www.idsia.ch/~juergen/everything/html.html

http://www.idsia.ch/~juergen/toesv2/

Received on Tue Nov 13 2001 - 03:07:14 PST

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