5 ms·

> Engineers can build probabilistic models for patterns of pixel colors from one frame to the next. The models make it possible to calculate the Shannon entropy

> Engineers can build probabilistic models for patterns of pixel colors from one frame to the next. The models make it possible to calculate the Shannon entropy [...] That value tells you the limit of “lossless” compression — the absolute most the movie can be compressed before you start to lose information about its contents. While this is generally true in practice, strictly speaking the shortest possible encoding of a sequence of bits could be smaller than this would suggest, since it's possible a pattern exists that has escaped notice. For example: the first 10 billion digits of pi pass statistical tests for randomness, but can be generated by a short program which calculates them until the desired length is reached, in effect "compressing" them to the length of the generator program. Because of considerations like this, Algorithmic Information Theory[1] equates the information content of a bit sequence with the length of the shortest program which will generate it - though this has the drawback of being generally uncomputable - an intriguingly different paradigm. 1: see https://en.wikipedia.org/wiki/Algorithmic_information_theory https://en.wikipedia.org/wiki/Algorithmic_information_theory

Eddy_Viscosity2 4y ago
Could a smaller program be written that could generate the code that generates the digits of pi? So the code that writes the code is the smallest information content? I wonder how many times this could recurse before there is a limit..
- zbobet2012 4y ago
  That's the https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity. It's uncomputable in general.
  - Eddy_Viscosity2 4y ago
    Nice, this is exactly what I meant. Actually kind of proud of myself for having a similar thought as Kolmogovov.
corey_moncure 4y ago
OK but "decompression" takes infinite time
- ketralnis 4y ago
  > the first 10 billion digits of pi No it doesn't, you program you generate produces the first 10 billion and then stops
abetusk 4y ago
You're not considering the exchange for space versus time. A short program may be able to compute the digits of pi to the accuracy you want but you're discounting the runtime and subsequent resources it uses to compute those digits. Readers could be left with the feeling that somehow you can get information for free, which is not the case. I can't start a program that prints all strings and claim I've achieved ideal compression because the desired output is among one of the strings printed. It's not just incomputability but the resources involved. I'm only barely familiar with Kolmogorov complexity and, as you point out, it looks like this is what Algorithmic Information theory is designed for but even in those scenarios, there's clearly a push and pull between run time and memory. As a heuristic, I tend to think of there being a sort of conservation law at work where sacrificing space will increase run-time and vice-versa.
- vba616 4y ago
  >I can't start a program that prints all strings and claim I've achieved ideal compression because the desired output is among one of the strings printed. I don't follow why this is an example of run time mattering. It sounds like an example of not including crucial information in your "compressed" output to enable decoding. You'd have to have a pointer into your sequence. Also, why wouldn't consideration of run time be a free choice people make? I vaguely remember trying some allegedly state of the art compressors and finding them extremely slow. Probably in the PPM family. Theoretically, people are sometimes interested in the maximum compression no matter how much it takes in resources.
  - svnt 4y ago
    If at the fastest speed a computer can physically operate the program would take longer than the expected duration of the universe, I believe we can safely say it does not usefully represent the information, even though in mathematical relationship it may seem to. Less absurdly, if the program takes longer to run than the MTBF of the computer it operates on, we can say the same thing with some probability. It’s a roundabout way of saying that what seems to work in math isn’t always possible useful or functional in material reality. Since Kolmogorov seems to be pointing in this direction of blurring computation in material reality with mathematical information it seems worth considering.
svnt 4y ago
I’ll ask it here since I’ve not seen it mentioned anywhere: the Kolmogorov work is interesting, but doesn’t it exclude the information necessary to produce a team of educated humans, a universal computer, a programming language, and a compiler/interpreter, at least? In a brief reading AIT seems to assume a universal Turing machine should exist by natural law.
- ttctciyf 4y ago
  Regards the interpreter aspect, that is dealt with by fixing some universal Turing machine - call it U - which runs all the programs considered, so that the program length of U becomes a constant which can either be factored out or reduced to insignificance by considering programs and strings with length much greater than U's. It is still a fly in the theoretical ointment that the K complexity of a given specific string might differ under different choices of U, not least because programs that encode some string might find chunks of it inside a specific U, like a program which prints the BIOS signon of a particular firmware could be shorter when running on that firmware. Regards the biological / sociological aspects you mention, I think the theoretical framework requires only the bare existence of some UTM with a finite size. If it is really Universal, you could just run the program which produces human society on it until we reach the present, I guess :)
  - svnt 4y ago
    Ha! Thanks for your insights. It does seem like a significant gap between the theory/maths and the implementation.
- dawnofdusk 4y ago
  There is no problem with assuming such a Turing machine exists so long as you compare only measurements of information with respect to that Turing machine. Generally what is relevant to study is entropy differences anyway. I don't know much about AIT in specific, but it seems that Chaitin 1975 (https://dl.acm.org/doi/10.1145/321892.321894 https://dl.acm.org/doi/10.1145/321892.321894) acknowledges this, as the algorithmic entropy differs from the usual Shannon entropy by a constant term, which one might imagine is the information needed to encode the Turing machine. I also wanted to mention that because you thought of the information theoretic implications of building a computer, etc., you might be interested to know that this kind of thinking is very interesting and cutting edge in biophysics. Organisms have to essentially build computers to do certain tasks, and in this way they must take into account both Shannon entropy (i.e., information in the abstract sense) and thermodynamic entropy! This is essentially the Maxwell's demon paradox (https://en.wikipedia.org/wiki/Maxwell's_demon) https://en.wikipedia.org/wiki/Maxwell's_demon).
rawoke083600 4y ago
Does the seed of a minecraft world fall into this category ?
- WJW 4y ago
  Yes, provided you use the same version of minecraft each time. The world generation algorithm might change from version to version, after all.
dawnofdusk 4y ago
I think your comments on encoding a sequence of bits/pi is a little misleading. For example, in the case of the first 10 billion digits of pi, you do not even need a program to calculate it. One can just use a lookup table which maps the digits 0 through 9 to the frequency they appear in 10 billion digits of pi, which is <40 bytes of data. You are confusing the entropy of the digits of pi, for which the order does not matter, and the entropy of the sequence of pi, for which the order does matter. In the latter, you would want compare the probability of observing the exact sequence of pi compared to other sequences of numbers. This is an entirely different question. Because the sequence of digits of pi is deterministic, its entropy is 0, i.e., if one had a machine from which you could sample "10-billion digit sequences of pi" you would get the same sequence every time. >strictly speaking the shortest possible encoding of a sequence of bits could be smaller than this would suggest, since it's possible a pattern exists that has escaped notice. If it is a deterministic pattern, then the entropy of the sequence is actually 0. Otherwise the existence of patterns is something that the entropy computation already takes into account, and is in fact the entire point. In practice, finite sample sizes introduces noise and means that we can only ever estimate the true entropy, and Jensen's inequality implies that all such estimates are higher than the true entropy of a system, so that we observe even deterministic sequences with noisy filters. This is perhaps the clearer version of your point.
- ttctciyf 4y ago
  Contrariwise, to me you seem to be the confused party. I am contrasting the compression given by lzw or zip as discussed in the article, which would be unable to significantly compress the bit sequence of pi, with the "compression technique" of simply calculating the same sequence (in order!) with a short program. A lookup table is irrelevant, since we're talking about printing out the first 10 billion pi digits in order by a simple algorithm for computing them, not about anything involving calculating their frequency or probability. (In any case, since those digits pass statistical randomness tests, the frequency distribution wouldn't tell you much, which is why zip-style compression fails on pi.) The point I'm making is that running a very short program can print a 10 billion digit sequence which stats-based compression methods would fail to significantly compress. The digits of pi happen to be a good example of this, but there are likely plenty of others. Regards the second part of your comment, the notion of a "deterministic pattern" is intriguing, but what does it mean? If you mean "not random" then in the algorithmic information world that equates to "can be printed by a program shorter than itself". Obviously any (including random) sequence can be printed by some program, but the presence of regularity (or "patterns" if you like) in a sequence allows shorter encodings, either by creating a dictionary of recurring subsequences, as in lzw or zip style compression, or by some other means as in the calculation of pi's digits. I suggest you read up on AIT or Kolmogorov complexity at the wikipedia links I posted to get an idea of what my comment was actually about :)

Eddy_Viscosity2 4y ago

Could a smaller program be written that could generate the code that generates the digits of pi? So the code that writes the code is the smallest information content? I wonder how many times this could recurse before there is a limit..

zbobet2012 4y ago
That's the https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity. It's uncomputable in general.
- Eddy_Viscosity2 4y ago
  Nice, this is exactly what I meant. Actually kind of proud of myself for having a similar thought as Kolmogovov.

corey_moncure 4y ago

OK but "decompression" takes infinite time

ketralnis 4y ago
> the first 10 billion digits of pi No it doesn't, you program you generate produces the first 10 billion and then stops

abetusk 4y ago

You're not considering the exchange for space versus time. A short program may be able to compute the digits of pi to the accuracy you want but you're discounting the runtime and subsequent resources it uses to compute those digits. Readers could be left with the feeling that somehow you can get information for free, which is not the case. I can't start a program that prints all strings and claim I've achieved ideal compression because the desired output is among one of the strings printed. It's not just incomputability but the resources involved. I'm only barely familiar with Kolmogorov complexity and, as you point out, it looks like this is what Algorithmic Information theory is designed for but even in those scenarios, there's clearly a push and pull between run time and memory. As a heuristic, I tend to think of there being a sort of conservation law at work where sacrificing space will increase run-time and vice-versa.

vba616 4y ago
>I can't start a program that prints all strings and claim I've achieved ideal compression because the desired output is among one of the strings printed. I don't follow why this is an example of run time mattering. It sounds like an example of not including crucial information in your "compressed" output to enable decoding. You'd have to have a pointer into your sequence. Also, why wouldn't consideration of run time be a free choice people make? I vaguely remember trying some allegedly state of the art compressors and finding them extremely slow. Probably in the PPM family. Theoretically, people are sometimes interested in the maximum compression no matter how much it takes in resources.
- svnt 4y ago
  If at the fastest speed a computer can physically operate the program would take longer than the expected duration of the universe, I believe we can safely say it does not usefully represent the information, even though in mathematical relationship it may seem to. Less absurdly, if the program takes longer to run than the MTBF of the computer it operates on, we can say the same thing with some probability. It’s a roundabout way of saying that what seems to work in math isn’t always possible useful or functional in material reality. Since Kolmogorov seems to be pointing in this direction of blurring computation in material reality with mathematical information it seems worth considering.

svnt 4y ago

I’ll ask it here since I’ve not seen it mentioned anywhere: the Kolmogorov work is interesting, but doesn’t it exclude the information necessary to produce a team of educated humans, a universal computer, a programming language, and a compiler/interpreter, at least? In a brief reading AIT seems to assume a universal Turing machine should exist by natural law.

ttctciyf 4y ago
Regards the interpreter aspect, that is dealt with by fixing some universal Turing machine - call it U - which runs all the programs considered, so that the program length of U becomes a constant which can either be factored out or reduced to insignificance by considering programs and strings with length much greater than U's. It is still a fly in the theoretical ointment that the K complexity of a given specific string might differ under different choices of U, not least because programs that encode some string might find chunks of it inside a specific U, like a program which prints the BIOS signon of a particular firmware could be shorter when running on that firmware. Regards the biological / sociological aspects you mention, I think the theoretical framework requires only the bare existence of some UTM with a finite size. If it is really Universal, you could just run the program which produces human society on it until we reach the present, I guess :)
- svnt 4y ago
  Ha! Thanks for your insights. It does seem like a significant gap between the theory/maths and the implementation.
dawnofdusk 4y ago
There is no problem with assuming such a Turing machine exists so long as you compare only measurements of information with respect to that Turing machine. Generally what is relevant to study is entropy differences anyway. I don't know much about AIT in specific, but it seems that Chaitin 1975 (https://dl.acm.org/doi/10.1145/321892.321894 https://dl.acm.org/doi/10.1145/321892.321894) acknowledges this, as the algorithmic entropy differs from the usual Shannon entropy by a constant term, which one might imagine is the information needed to encode the Turing machine. I also wanted to mention that because you thought of the information theoretic implications of building a computer, etc., you might be interested to know that this kind of thinking is very interesting and cutting edge in biophysics. Organisms have to essentially build computers to do certain tasks, and in this way they must take into account both Shannon entropy (i.e., information in the abstract sense) and thermodynamic entropy! This is essentially the Maxwell's demon paradox (https://en.wikipedia.org/wiki/Maxwell's_demon) https://en.wikipedia.org/wiki/Maxwell's_demon).

rawoke083600 4y ago

Does the seed of a minecraft world fall into this category ?

WJW 4y ago
Yes, provided you use the same version of minecraft each time. The world generation algorithm might change from version to version, after all.

dawnofdusk 4y ago

I think your comments on encoding a sequence of bits/pi is a little misleading. For example, in the case of the first 10 billion digits of pi, you do not even need a program to calculate it. One can just use a lookup table which maps the digits 0 through 9 to the frequency they appear in 10 billion digits of pi, which is <40 bytes of data. You are confusing the entropy of the digits of pi, for which the order does not matter, and the entropy of the sequence of pi, for which the order does matter. In the latter, you would want compare the probability of observing the exact sequence of pi compared to other sequences of numbers. This is an entirely different question. Because the sequence of digits of pi is deterministic, its entropy is 0, i.e., if one had a machine from which you could sample "10-billion digit sequences of pi" you would get the same sequence every time. >strictly speaking the shortest possible encoding of a sequence of bits could be smaller than this would suggest, since it's possible a pattern exists that has escaped notice. If it is a deterministic pattern, then the entropy of the sequence is actually 0. Otherwise the existence of patterns is something that the entropy computation already takes into account, and is in fact the entire point. In practice, finite sample sizes introduces noise and means that we can only ever estimate the true entropy, and Jensen's inequality implies that all such estimates are higher than the true entropy of a system, so that we observe even deterministic sequences with noisy filters. This is perhaps the clearer version of your point.

ttctciyf 4y ago
Contrariwise, to me you seem to be the confused party. I am contrasting the compression given by lzw or zip as discussed in the article, which would be unable to significantly compress the bit sequence of pi, with the "compression technique" of simply calculating the same sequence (in order!) with a short program. A lookup table is irrelevant, since we're talking about printing out the first 10 billion pi digits in order by a simple algorithm for computing them, not about anything involving calculating their frequency or probability. (In any case, since those digits pass statistical randomness tests, the frequency distribution wouldn't tell you much, which is why zip-style compression fails on pi.) The point I'm making is that running a very short program can print a 10 billion digit sequence which stats-based compression methods would fail to significantly compress. The digits of pi happen to be a good example of this, but there are likely plenty of others. Regards the second part of your comment, the notion of a "deterministic pattern" is intriguing, but what does it mean? If you mean "not random" then in the algorithmic information world that equates to "can be printed by a program shorter than itself". Obviously any (including random) sequence can be printed by some program, but the presence of regularity (or "patterns" if you like) in a sequence allows shorter encodings, either by creating a dictionary of recurring subsequences, as in lzw or zip style compression, or by some other means as in the calculation of pi's digits. I suggest you read up on AIT or Kolmogorov complexity at the wikipedia links I posted to get an idea of what my comment was actually about :)