4 ms·

The general principle here, which is quite foundational in computer science and the theory of complexity, is that of "Kolmogorov complexity". The Kolmogorov com

by OskarS 7y ago

The general principle here, which is quite foundational in computer science and the theory of complexity, is that of "Kolmogorov complexity". The Kolmogorov complexity of a certain string (roughly speaking) is the shortest computer program needed to produce that string. Much like Turing's halting problem or Church's beta-equivalence, it is impossible to write a program to calculate the Kolmogorov complexity in general. It is "non-computable".

ramses0 7y ago
That does a lot to explain why programming is so hard. "If you know the output you'd like, it's impossible to know how much code it will take to get there."
- lisper 7y ago
  Not quite. What is impossible to know is if you have the shortest solution.
derefr 7y ago
And yet, we can fairly-easily upper-bound Kolmogorov complexity (often, we believe, quite tightly, though we can’t know for sure.) Quoting Wikipedia: > It is straightforward to compute upper bounds for K(s) – simply compress the string s with some method, implement the corresponding decompressor in the chosen language, concatenate the decompressor to the compressed string, and measure the length of the resulting string – concretely, the size of a self-extracting archive in the given language. This is analogous (but not exactly) to the Travelling Salesman Problem: we “can’t” (in the case of Kolmogorov complexity, literally cannot) get the exact number, but getting a nearly perfect estimate of the number has cheap-and-easy algorithms. It’s fun to think about what an exact solution to computable Kolmogorov complexity would “mean”, though, sort of like it’s fun to think about the consequences of https://en.wikipedia.org/wiki/Hypercomputation https://en.wikipedia.org/wiki/Hypercomputation: as a consequence of calculating the Kolmogorov complexity, you’d be optimally compressing the input data, identifying every possible nuance of self-similarity in the input, no matter on what level of abstraction it occurred. The intermediate model of the informational content required to construct the compressor would be immense—possibly a description of all mathematical theorems in the relevant axiom system, and all scientific laws governing the relevant generator-of-structure (e.g. physics, chemistry, biology, human psychology, etc.) Such a system really could “understand the universe from a grain of sand.”
- perl4ever 7y ago
  If you take the first million digits of pi, and compress it with, say, bzip2, you get a file of about 420KB. This is pretty good in one sense - an 8 bit byte that stores a decimal digit can store 3.3 bits of information, right? As such, you would expect output to be 3.3/8 or about 42%. But obviously that 420KB + a decompressor is nowhere near a minimal program. I've always been fascinated with the Mandelbrot/Julia sets and where that information comes from as well.
whatshisface 7y ago
>it is impossible to write a program to calculate the Kolmogorov complexity in general. It is "non-computable". I don't get it, why couldn't you "simply" iterate through every program shorter than the string you're trying to compress, compiling and running each while discarding the ones with the wrong output and halting when you either find a working program or run out of shorter strings to try? Edit: Oh, I get it now, you can't tell whether or not a given long-running program will eventually produce the target string without solving its halting problem.
- deleted 7y ago
  [deleted]
- OskarS 7y ago
  > Edit: Oh, I get it now, you can't tell whether or not a given long-running program will eventually produce the target string without solving its halting problem. Exactly right! I kinda think that these non-computable problems are all sort-of the same problem, just viewed from different angles.

by OskarS 7y ago

ramses0 7y ago

That does a lot to explain why programming is so hard. "If you know the output you'd like, it's impossible to know how much code it will take to get there."

lisper 7y ago
Not quite. What is impossible to know is if you have the shortest solution.

derefr 7y ago

And yet, we can fairly-easily upper-bound Kolmogorov complexity (often, we believe, quite tightly, though we can’t know for sure.) Quoting Wikipedia: > It is straightforward to compute upper bounds for K(s) – simply compress the string s with some method, implement the corresponding decompressor in the chosen language, concatenate the decompressor to the compressed string, and measure the length of the resulting string – concretely, the size of a self-extracting archive in the given language. This is analogous (but not exactly) to the Travelling Salesman Problem: we “can’t” (in the case of Kolmogorov complexity, literally cannot) get the exact number, but getting a nearly perfect estimate of the number has cheap-and-easy algorithms. It’s fun to think about what an exact solution to computable Kolmogorov complexity would “mean”, though, sort of like it’s fun to think about the consequences of https://en.wikipedia.org/wiki/Hypercomputation https://en.wikipedia.org/wiki/Hypercomputation: as a consequence of calculating the Kolmogorov complexity, you’d be optimally compressing the input data, identifying every possible nuance of self-similarity in the input, no matter on what level of abstraction it occurred. The intermediate model of the informational content required to construct the compressor would be immense—possibly a description of all mathematical theorems in the relevant axiom system, and all scientific laws governing the relevant generator-of-structure (e.g. physics, chemistry, biology, human psychology, etc.) Such a system really could “understand the universe from a grain of sand.”

perl4ever 7y ago
If you take the first million digits of pi, and compress it with, say, bzip2, you get a file of about 420KB. This is pretty good in one sense - an 8 bit byte that stores a decimal digit can store 3.3 bits of information, right? As such, you would expect output to be 3.3/8 or about 42%. But obviously that 420KB + a decompressor is nowhere near a minimal program. I've always been fascinated with the Mandelbrot/Julia sets and where that information comes from as well.

whatshisface 7y ago

>it is impossible to write a program to calculate the Kolmogorov complexity in general. It is "non-computable". I don't get it, why couldn't you "simply" iterate through every program shorter than the string you're trying to compress, compiling and running each while discarding the ones with the wrong output and halting when you either find a working program or run out of shorter strings to try? Edit: Oh, I get it now, you can't tell whether or not a given long-running program will eventually produce the target string without solving its halting problem.

deleted 7y ago
[deleted]
OskarS 7y ago
> Edit: Oh, I get it now, you can't tell whether or not a given long-running program will eventually produce the target string without solving its halting problem. Exactly right! I kinda think that these non-computable problems are all sort-of the same problem, just viewed from different angles.