Re: Provable vs Computable (post not done)

From: Hal Ruhl <>
Date: Fri, 04 May 2001 18:23:20 -0700

Sorry, some how my mailer decided I wanted to send this.
Clearly it is not done.

Dear Juergen:

I am not so much interested in provability as I am in whether or not the
"noise" in a universes history is pseudorandom or random and forging an .

At 5/4/01, you wrote:

>Which are the logically possible universes? Max Tegmark mentioned
>a somewhat vaguely defined set of ``self-consistent mathematical
>structures,'' implying provability of some sort. The postings of Bruno
>Marchal and George Levy and Hal Ruhl also focus on what's provable and
>what's not.
>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?
>I believe the provability discussion distracts a bit 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 unprovable aspects.
>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 element
>of an ordered list of all possible program prefixes halts. 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.
>Such a virtual reality or universe is perfectly well-defined. At some
>point each history prefix will remain stable forever. Even if we know p
>and q, however, in general we will never know for sure whether some q(n)
>that is still zero won't flip to 1 at some point, because of Goedel etc.
>So this universe features lots of unprovable aspects.
>But why should this lack of provability matter? It does not do any harm.
>Note also that observers evolving within the universe may write
>books about all kinds of unprovable things; they may also write down
>inconsistent axioms; etc. All of this is computable though, since the
>entire universe history is. So again, why should provability matter?
>Juergen Schmidhuber
Received on Fri May 04 2001 - 15:27:32 PDT

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