4 ms·

...the output of a simulation of a chaotic system is highly compressible... Is that really true? Losslessly? Do you mean the entire phase space, or the sequenc

...the output of a simulation of a chaotic system is highly compressible... Is that really true? Losslessly? Do you mean the entire phase space, or the sequence generated on any given run? Because I was under the impression that what distinguishes a chaotic system is that the output cannot be predicted in any way other than running the simulation (the article uses the word 'random', but it might be better to say 'unpredictable'). Compressibility relies on exploiting regularities, and regularity is predictability, isn't it?

Strilanc 14y ago
See: Kolmogorov Complexity ( http://en.wikipedia.org/wiki/Kolmogorov_complexity http://en.wikipedia.org/wiki/Kolmogorov_complexity ) The program that simulates the chaotic system is shorter than the unbounded amount of output being generated, and counts as a compression of the output.
- Gravityloss 14y ago
  Sure, but that is kind of circular. I guess in other words, the more interesting question is this: can we generate hard to compress pseudorandom sequences with simple algorithms - if the algorithm description by itself can not be used as "compression"?
  - MostAwesomeDude 14y ago
    Absolutely. Consider any number which can be expressed as a patterned continued fraction, like pi or e. pi's digits are such that it is very hard to compress, but it is absolutely trivial to generate. (http://en.wikipedia.org/wiki/Continued_fraction http://en.wikipedia.org/wiki/Continued_fraction)
    - Fargren 14y ago
      How is the algorithm that generates the digits of pi a compressed form of pi? It gives me all the information about the number in finite amount of time. In randomness theory, the definition of the most compressed form of a sequence S is, given a computer C, the shortest program with output S in C. So the program that generates the output of the simulation of the pendulums is a compression of it's output. Since it's and infinite sequence that can be compressed into a finite program, it is not random from the perspective of information theory or randomness theory.
    - AnthonyMouse 14y ago
      >Consider any number which can be expressed as a patterned continued fraction, like pi or e. pi's digits are such that it is very hard to compress, but it is absolutely trivial to generate. You're confusing theoretical compressibility with the actual compression ratios you get when you put a string through typical compression functions. Here's a different example. Suppose you have ASCII text encrypted with AES with the AES decryption key appended to it. Run that through gzip and you'll probably get output which is larger than the input. But here's a different compression algorithm that will work much better: Decrypt the encrypted data with the key and then compress the plaintext with gzip. It isn't that the original string is of the sort that can't be compressed, it's that you need a compression function which is suited to the input. Pi is like that. Compare this to other strings, like the output of an environmental hardware random number generator, which will almost always be totally incompressible whatsoever.
  - Fargren 14y ago
    No. We can't. If the algorithm that generates the sequence is simple, lets call it algorithm X, then a concise way of expressing the string is "the output of algorithm X". That expression losslesly compresses the output, and it's just a few characters longer than the algorithm itself. Randomness theory and information theory study such things. If you add a rule such as not using Algorithm X, it's trivial to create an Algorithm Y that generates the same output and it's barely any longer than X. For example, by adding any meaningless instruction at the start of algorithm X. Of course, discovering what the shortest expression for a given sequence is is not a computable problem. So we can't always know if we've found the best form of compression for a sequence, we can only find an upper bound.
  - Dylan16807 14y ago
    What's a 'simple' algorithm? You can fit a brainfuck interpreter into a single tweet, and from there use the data to handle any other computation. Or does 'simple' mean like an extractor for a standard archive file? Did you know that RAR is turing complete? Maybe 'simple' has to be defined by limiting how much execution time you have per output byte?
- vannevar 14y ago
  That seems like another way of wording what I said, which is that there is no way to predict the output other than by running the algorithm that generates it. If you are presented only with the string representing the unbounded output, is there any way to reconstruct the algorithm from it? If not, then I would say that the string itself is incompressible; in that case only the string plus the algorithm is compressible in the way you describe.
yk 14y ago
The difference between an chaotic and an non chaotic system is, how small perturbations propagate. In a regular system, you get essentially the same result, even if you start from slightly different initial conditions. In a chaotic one, small perturbations will amplify and therefore the system will end up in a very different state from nearly the same initial conditions. ( And if there is an experimental error, then the final state is essentially random.)

Strilanc 14y ago

See: Kolmogorov Complexity ( http://en.wikipedia.org/wiki/Kolmogorov_complexity http://en.wikipedia.org/wiki/Kolmogorov_complexity ) The program that simulates the chaotic system is shorter than the unbounded amount of output being generated, and counts as a compression of the output.

Gravityloss 14y ago
Sure, but that is kind of circular. I guess in other words, the more interesting question is this: can we generate hard to compress pseudorandom sequences with simple algorithms - if the algorithm description by itself can not be used as "compression"?
- MostAwesomeDude 14y ago
  Absolutely. Consider any number which can be expressed as a patterned continued fraction, like pi or e. pi's digits are such that it is very hard to compress, but it is absolutely trivial to generate. (http://en.wikipedia.org/wiki/Continued_fraction http://en.wikipedia.org/wiki/Continued_fraction)
  - Fargren 14y ago
    How is the algorithm that generates the digits of pi a compressed form of pi? It gives me all the information about the number in finite amount of time. In randomness theory, the definition of the most compressed form of a sequence S is, given a computer C, the shortest program with output S in C. So the program that generates the output of the simulation of the pendulums is a compression of it's output. Since it's and infinite sequence that can be compressed into a finite program, it is not random from the perspective of information theory or randomness theory.
  - AnthonyMouse 14y ago
    >Consider any number which can be expressed as a patterned continued fraction, like pi or e. pi's digits are such that it is very hard to compress, but it is absolutely trivial to generate. You're confusing theoretical compressibility with the actual compression ratios you get when you put a string through typical compression functions. Here's a different example. Suppose you have ASCII text encrypted with AES with the AES decryption key appended to it. Run that through gzip and you'll probably get output which is larger than the input. But here's a different compression algorithm that will work much better: Decrypt the encrypted data with the key and then compress the plaintext with gzip. It isn't that the original string is of the sort that can't be compressed, it's that you need a compression function which is suited to the input. Pi is like that. Compare this to other strings, like the output of an environmental hardware random number generator, which will almost always be totally incompressible whatsoever.
- Fargren 14y ago
  No. We can't. If the algorithm that generates the sequence is simple, lets call it algorithm X, then a concise way of expressing the string is "the output of algorithm X". That expression losslesly compresses the output, and it's just a few characters longer than the algorithm itself. Randomness theory and information theory study such things. If you add a rule such as not using Algorithm X, it's trivial to create an Algorithm Y that generates the same output and it's barely any longer than X. For example, by adding any meaningless instruction at the start of algorithm X. Of course, discovering what the shortest expression for a given sequence is is not a computable problem. So we can't always know if we've found the best form of compression for a sequence, we can only find an upper bound.
- Dylan16807 14y ago
  What's a 'simple' algorithm? You can fit a brainfuck interpreter into a single tweet, and from there use the data to handle any other computation. Or does 'simple' mean like an extractor for a standard archive file? Did you know that RAR is turing complete? Maybe 'simple' has to be defined by limiting how much execution time you have per output byte?
vannevar 14y ago
That seems like another way of wording what I said, which is that there is no way to predict the output other than by running the algorithm that generates it. If you are presented only with the string representing the unbounded output, is there any way to reconstruct the algorithm from it? If not, then I would say that the string itself is incompressible; in that case only the string plus the algorithm is compressible in the way you describe.

yk 14y ago

The difference between an chaotic and an non chaotic system is, how small perturbations propagate. In a regular system, you get essentially the same result, even if you start from slightly different initial conditions. In a chaotic one, small perturbations will amplify and therefore the system will end up in a very different state from nearly the same initial conditions. ( And if there is an experimental error, then the final state is essentially random.)