RE: Is the universe computable

From: David Barrett-Lennard <dbl.domain.name.hidden>
Date: Wed, 21 Jan 2004 09:27:17 +0800

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:hal.domain.name.hidden]
> Sent: Tuesday, 20 January 2004 1:24 AM
> To: everything-list.domain.name.hidden
> 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 - 20:29:06 PST