Re: Provable vs Computable

From: Hal Ruhl <>
Date: Sun, 06 May 2001 22:35:57 -0700

Dear Juergen:

My little isomorphism tree did not transmit very well.

The second column heading should read: "horizontal on this page isomorphic
The third should read: "the isomorphically linked string"

All the binary strings should be under the third column.



         * <
::: > * = 0
                                         {*} =
                                       {*,{*}} =
                                    {*,{*},{*,{*}}} =
                                           : :
                                           : :
and inactive
"vertical" isomorphic
to this string
and inactive
"vertical" isomorphic
to this string


The page horizontal isomorphic links on the right hand side are the usual

The page vertical isomorphic links are the ones I have used in my
model. Each of these vertical isomorphic links [there can be more than one
per string] uses a portion of the string to which it links to define its
self contained FAS. The rest of the string determines the associated state
of the vertical isomorphism. The current state of a vertical isomorphism
is the active link for that isomorphism. All inactive links are either
past or future states of isomorphisms. The self contained FAS of a
particular vertical isomorphism determines which links are acceptable
immediate successor states of that isomorphism. Depending on the nature of
the FAS there could be more than one acceptable immediate successor state
for that isomorphism.

The symbol "< ::: >" indicates that the isomorphism tree structure - "The
Everything" - vanishes upon occasion and the anisomorphic null set - "The
Nothing" - resumes. This is the E/N alternation. Neither the anisomorphic
null set nor the isomorphism tree since they both contain no information
can internally address the unavoidable question of their own
durability. This bilateral incompleteness drives the E/N
alternation. The alternation since it destroys any record of the previous
mix of active/inactive vertical isomorphic links causes a new random
active/inactive mix each time the isomorphism tree resumes. This avoids a
"selected" structure to The Everything.

In order for a vertical isomorphic link to transfer to another string both
the current link and an acceptable successor link must be simultaneously
active. The transfer inactivates the prior link. Vertical isomorphic
links driven active or inactive by the E/N alternation absent an active
acceptable successor is simply in stasis. For a transfer to take place
both the current and acceptable successor link must be simultaneously
active. It is the transfer that is an "event" to an isomorphism.

Are UD's or other such string generating machines vertical isomorphic
links? I think so if I understand them correctly. Simply concatenate all
the output strings of a UD so that successor vertical link shifts are just
based on very localized regions of the overall string.

I also think this process is similar to "observer moments" if "observer
moment" means active links.

Since the null set just "is" then the process may satisfy the idea that the
Everything just "is".
It is the isomorphic tree that undergoes change.

Now I see nothing wrong with FAS that have a "do not care" content to their
rules determining acceptable successor links.

My goal is to try to show that universes [vertical isomorphic links] that
can support SAS have at least some "do not care" content in the rules. To
do this I turn to Chaitin and explore the viability of deterministic
cascades. By deterministic I mean each state has only one possible prior
and one possible successor - the computational exercise is by definition
elegant. However, the complexity of the strings to which such sequences
form isomorphic links must relentlessly increase . This produces a
conflict between the idea of cascade and the idea of a limit on the
complexity of the string that the finite self contained FAS can determine
is acceptable using only elegant programs.

This conflict is resolved by an injection of complexity into the FAS from

It is also reasonable that some of these FAS are subject to the
incompleteness of Godel.

So it is just Chaitin and Godel that interest me as far as "proof" is

Other than the above I really can not find a simple thing in your post
below with which I disagree.



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 Sun May 06 2001 - 19:44:44 PDT

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