[coldtea]

>Think of a series of random bits that can be either 0 or 1 with equal probability. How likely is it that they are all 0 or all 1? Not very likely. There is exactly one configuration. How likely is it that they have a specific configuration of 0 and 1? Equally likely.

Well, there are only 2 states with all 1 or all 0.

But there are 2^N states of mixed 1 and 0.

Even if you treat the sets of bits as opaque items, and pick one from a bucket, I'd expect getting one of the 2^N - 2 configurations to be a far more likely outcome than one of the 2 remaining.

In fact, we could bet on it...

[jbay808]

But there's only one state that is 10010001111110101000.

[coldtea]

Sure, but that's irrelevant.

There are billions that are similar, and only one that's all 0.

[jbay808]

"similar" is in the eye of the observer! This fact should be especially clear in the context of bit strings. If 10010001111110101000 is my login password, don't be surprised if other permutations fail to grant you access, even if you have the correct number of 1's and 0's.

[coldtea]

>"similar" is in the eye of the observer!

Nope, also similar in algorithmic complexity theory (e.g. counting compressibility).

[jbay808]

That's a very good, and deep, point, and I agree that there is something important there. However, algorithmic complexity is still only defined relative to an arbitrary reference computer. If my reference computer happens to, in hardware, XOR its inputs and outputs with the bitstring 10010001111110101000, then (in terms of bits that end up represented on the drive), that will be the one that has the lowest algorithmic complexity, although the algorithm might think that it's outputting all 0's.