News for hackers. Stuff that matters.
Re:Chaitin's Constant by whatshisface on Monday January 20, 2020 @11:46AM (#22100048)
>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.

Re:Chaitin's Constant by OskarS on Wednesday January 22, 2020 @11:47AM (#22119157)
> 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.