Does this help... Let f(x) be a predicate on positive integer x.

Let pn = |{ x <= n | f(x) }| / n (ie the fraction of the first n positive integers that satisfy the predicate) I propose that we define the probability of f as P(f) = p if pn converges to p. This allows us to say the probability that an integer is even is 0.5, or the probability that an integer is a perfect square is 0. - David > -----Original Message----- > From: Hal Finney [mailto:[EMAIL PROTECTED] > Sent: Tuesday, 20 January 2004 1:24 AM > To: [EMAIL PROTECTED] > 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