Re: Is the universe computable

From: Stephen Paul King <stephenk1.domain.name.hidden>
Date: Mon, 19 Jan 2004 13:19:30 -0500

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?

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 Mon Jan 19 2004 - 14:11:45 PST