RE: Is the universe computable

From: Kory Heath <kory.heath.domain.name.hidden>
Date: Mon, 19 Jan 2004 03:38:08 -0500

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?

I don't mean to sound so critical - I'm genuinely asking for information. I
know virtually nothing about measure theory. Is there some well-defined way
of getting different measures for countably infinite sub-sets of a
countably infinite ensemble?

-- Kory
Received on Mon Jan 19 2004 - 03:40:58 PST