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

From: Wei Dai <weidai.domain.name.hidden>

Date: Fri, 2 Nov 2001 16:19:24 -0800

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?

*> 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?

*> 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?

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?

Received on Fri Nov 02 2001 - 16:21:19 PST

Date: Fri, 2 Nov 2001 16:19:24 -0800

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

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?

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?

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?

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?)

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?

Received on Fri Nov 02 2001 - 16:21:19 PST

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