[Cryptography] Entropy is forever ...

[R. Hirschfeld]

>> On the other hand, there is a notion of algorithmic complexity of an
>> individual string  [1]
>
> Sorry, no, there is not any notion of complexity or entropy
> that is inherent to an individual string.

Well, I have no interest in arguing the point (I just pointed it out
because I thought might find it interesting) nor do I disagree with
what you wrote in your previous email, but I think that if you look at
the work of Solomonoff, Kolmogorov, Chaitin, et. al. you'll find that
this is what they describe.  You might not find it a useful notion,
but the notion does exist.

http://en.wikipedia.org/wiki/Kolmogorov_complexity gives an overview
although I'm not sure how good it is.


> For any two compressors [C1] and [C2] there is a uniform
> bound on the difference between K[C1](...) and K[C2](...).
> Sometimes the difference doesn't matter, but sometimes it
> matters a great deal.

Interestingly, when the notion of Kolmogorov randomness is extended
to infinite strings, the particular universal description language
doesn't matter.


>> There are formal relationships between K-randomness and entropy.
>
> The formal relationship is simple and easily stated.
> Entropy is defined in terms of probability.  If you
> have a probability distribution over programs, it
> induces a probability distribution over strings ...
> or it would, if it didn't run afoul of the halting
> problem.

I was thinking of a theorem of Brudno (I think) that I had seen
mentioned somewhere but I don't remember the details.


> Whether the probability constructed in this way bears
> any relationship to the real-world probability of the
> relevant strings is another question entirely.  There
> are lots of probability measures in this world.  Just
> because you have found "some" probability measure does
> not mean it is the right one.  Calling it a "universal"
> probability measure doesn't make it an all-purpose
> probability measure, or even a decent approximation
> to the correct probability measure.

With "universal" I wasn't referring to the probability measure but
rather to the programming/description language (similar to the
notion of a universal Turing machine).

I guess in some cases the "right" or "correct" probability measure is
a philosophical question.