- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

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

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

that

will

strings,

is

with

correspondence

squares

two

to

that

second.

justify

Received on Tue Jan 20 2004 - 20:29:06 PST

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:09 PST
*