3 ms·
>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" itera
by 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.