Re: does complexity tell us that there are probably exploits?

From: Peter de Blanc (peter.deblanc@verizon.net)
Date: Mon Aug 22 2005 - 19:24:56 MDT

On Mon, 2005-08-22 at 17:15 -0700, Daniel Radetsky wrote:
> Vassar wants to say that despite my objections, we ought worry about
> exploits
> but not ninja hippos because the claim "there are exploits" has a
> higher prior
> probability than "there are ninja hippos." This is because, according
> to
> Vassar, the Kolmogorov complexity of e, the first proposition, is
> greater than
> the complexity of h, the second proposition.

I think his point was that the class of phenomena which we would call
"exploits" is much larger than the class of phenomena which we would
call "ninja hippos."

By the way, it doesn't really make sense to speak of the Kolmogorov
complexity of a set of possible outcomes as a means to determine the
probability that the actual outcome will fall within that set.
Kolmogorov complexity is only useful for assigning priors to *specific*
outcomes.

For example, given the sequence 1, 2, ...,

the statement "3 or 4 is next" is less complex than the statement "3, 4,
or 5 is next," but clearly the latter statement at least as likely as
the former. It would make more sense to compare the Kolmogorov
complexity of "1, 2, 3" with the Kolmogorov complexity of "1, 2, 4" and
"1, 2, 5."

Given infinite resources, what you should REALLY do is generate all
possible programs, ordered by size, and assign a prior to each program:
maybe something like 2^-n, where n is the index of the program (starting
with 1). Then the probability that the next digit is 3 is the sum of the
priors of all programs whose output begins with "1, 2, 3," divided by
the sum of the priors of all programs whose output begins with "1, 2."

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