Hacker News new | ask | show | jobs
by PhilipRoman 741 days ago
Entropy of a particular string isn't a rigorous mathematical idea, since by definition the string which is known can only take one value, the "entropy" is therefore zero bits. The reason why we can distinguish non-random data from random is that only a small subset of all possible states are considered useful for humans, and since we have an idea what that subset looks like, we can try to estimate what process was used to generate a particular string.

There are of course statistical tests like https://en.wikipedia.org/wiki/Diehard_tests, which are good enough for distinguishing low entropy and high entropy data, but current pseudo-random number generators have no problem passing all of those, even though their actual "entropy" is just the seed plus approximate the complexity of the algorithm.
1 comments
josephg 741 days ago
If you’re looking for a rigorous mathematical idea, what people are trying to measure is the Kolmogorov complexity of the code. Measuring the compressed length is a rough estimate of that value.

https://en.m.wikipedia.org/wiki/Kolmogorov_complexity

link
PhilipRoman 741 days ago
Yes, although (and here my understanding of Kolmogorov complexity ends) it still depends heavily on the choice of language and it seems to me like "aaaaaaaaa" is only less complex than "pSE+4z*K58" due to assuming a sane, human-centric language which is very different from the "average" of all possible languages. Which then leads me to wonder how to construct an adversarial turing-complete language which has unintuitive Kolmogorov complexities.
link
josephg 741 days ago
> due to assuming a sane, human-centric language

There’s no requirement that the K-complexity is measured in a human centric language. Arguably all compression formats are languages too, which can be executed to produce the decompressed result. They are not designed to be human centric at all, and yet they do a surprisingly decent job at providing an estimate (well, upper bound) on Kolmogorov complexity. - As we can see in this program.

link
kqr 741 days ago
Kolmogorov complexity conventionally refers to the Turing machine as the base for implementation. This indeed makes repeated letters significantly less complex than that other string. (If you want intuition for how much code is needed to do something on a Turing machine, learn and play around a bit with Brainfuck. It's actually quite nice for that.)
link