RE: Is the universe computable

From: Hal Finney <hal.domain.name.hidden>
Date: Mon, 19 Jan 2004 09:23:34 -0800

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 - 12:25:16 PST