Re: how to do something with really small probability?

From: Wei Dai (
Date: Fri Nov 02 2007 - 04:01:30 MDT

Eliezer S. Yudkowsky wrote:
> I don't see it as having anything to do with the algorithm
> information. It's a problem of having to generate 3^^^3 random bits
> in the first place. If you can repeat an action 3^^^3 times and you
> can flip a quantum coin that many times, you're home free; if you live
> in a non-branching universe then you can't do anything random period.

Ignoring the non-branching universe for the moment, how do you know that
each quantum coin flip is actually independent from all of the others? If
the flips are not independent, it's possible that your 3^^^3 bits contains
only say 2^100 bits of information but you have no way of telling the
difference. (What I mean is that the laws of physics are such that quantum
coin flips only appear to be independent, but aren't really.)

I'll put this in more formal terms to make it clearer. Let P(x) be the
probability that x is the output of a uniformly random program. Let SI be
the program of a superintelligence such that P(SI) > 1/2^(2^80). (That had
better be true, or we have no hope of ever seeing this SI.) Now is it
possible that SI can take an arbitrary string x and tell us whether P(x) <
1/2^(2^100)? The answer is no, because suppose it could, then we can find
the lexicographically first string S with P(S) < 1/2^(2^100) by writing a
program that uses SI as a subroutine and queries it with all possible
strings in lexicographical order until the SI answers "yes", but since this
program isn't much larger than SI itself, that implies P(S) can't be much
smaller than 1/2^(2^80) which is a contradiction.

This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:00 MDT