3 ms·

See: Kolmogorov Complexity ( http://en.wikipedia.org/wiki/Kolmogorov_complexity http://en.wikipedia.org/wiki/Kolmogorov_complexity ) The program that simulates

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.

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.