Re: Is the universe computable

From: Bruno Marchal <marchal.domain.name.hidden>
Date: Tue, 20 Jan 2004 11:55:17 +0100

Dear Stephen,

At 13:19 19/01/04 -0500, Stephen Paul King wrote:
>Dear Hal, and Friends,
>
> Were and when is the consideration of the "physical resources" required
>for the computation going to obtain? Is my question equivalent to the old
>"first cause" question?


This is a good question for a physicalist. But if you accept the idea that
the very notion of time, energy, space are secondary and "logically emerges"
as a modality in the average memory of an average universal machine, then
that question is solved (once we get the right measure of course).
Now, about the measure, I am not convinced by Hal Finney's attempt
to define or compute it for reason we have already discussed a lot,
and which has just been recalled by George Levy in his last post.
I could add this: if you take the Universal Dovetailer (UD), you must take into
account the fact that he generates all version of all programs an infinite
number of times. For computer science reasons it is not possible to cut out
the vast redundancy of the codes in the production of the UD.
Now, this does not mean that some other reasons could not be invoked
for justifying the importance of "little" programs, though.

Regards,

Bruno


>Stephen
>
>----- Original Message -----
>From: "Hal Finney" <hal.domain.name.hidden>
>To: <everything-list.domain.name.hidden>
>Sent: Monday, January 19, 2004 12:23 PM
>Subject: RE: Is the universe computable
>
>
> > Kory Heath wrote:
> > > At 1/18/04, Hal Finney wrote:
> > > >Now consider all possible program tapes being run at the same time,
> > > >perhaps on an infinite ensemble of (virtual? abstract?) machines.
> > > >Of those, a fraction of 1 in 2^100 of those tapes will start with that
> > > >100 bit sequence for the program in question.
> > > [snip]
> > > >Now consider another program that is larger, 120 bits. By the same
> > > >reasoning, 1 in 2^120 of all possible program tapes will start with
>that
> > > >particular 120-bit sequence. And so 1/2^120 of all the executions will
> > > >be of that program.
> > >
> > > Yes, but if we're really talking about all possible finite bit strings,
> > > then the number of bit strings that begin with that 100 bit program is
> > > exactly the same as the number that begin with the 120 bit program -
> > > countably infinite. You can put them into a 1 to 1 correspondence with
>each
> > > other, just like you can put the integers into a 1 to 1 correspondence
>with
> > > the squares. The intuition that there must be more integers than squares
>is
> > > simply incorrect, as Galileo pointed out long ago. So shouldn't your two
> > > programs have the exact same measure?
> >
> > Well, I'm not a mathematician either, so I can't say for sure.
> > And actually it's worth than this, because I spoke of infinite program
> > tapes, so the number of programs is uncountably infinite.
> >
> > However, here is an alternate formulation of my argument which seems to
> > be roughly equivalent and which avoids this objection: create a random
> > program tape by flipping a coin for each bit. Now the probability that
> > you created the first program above is 1/2^100, and for the second,
> > 1/2^120, so the first program is 2^20 times more probable than the second.
> >
> > That seems correct, doesn't it? And it provides a similar way to justify
> > that the universe created by the first program has 2^20 times greater
> > measure than the second.
> >
> > Hal Finney
> >
> >
Received on Tue Jan 20 2004 - 05:55:07 PST