3 ms·
> Another thing to note is that Kolmogorov complexity of a string cannot be computed. There cannot exist a computer that will always guarantee the Kolmogorov co
by avmich 3y ago
> Another thing to note is that Kolmogorov complexity of a string cannot be computed. There cannot exist a computer that will always guarantee the Kolmogorov complexity for all the strings.
Sounds a bit puzzling. Surely for a particular programming language we can enumerate all programs, ordered by length etc. and check which is the shortest one giving the given string. So what's uncomputable here? For long strings that could take long time, but - ?
- MutualMisinfo 3y agoThe programs we check might not halt.
- floobertoober 3y agoWith a Turing complete language, you can't know whether a given program eventually yields the string, or continues indefinitely
- tromp 3y ago> So what's uncomputable here? Deciding whether the universal machine will ever halt on a particular input. I.e. the good old halting problem.
- deleted 3y ago[deleted]