4
$\begingroup$

Kolmogrov complexity is known to be uncomputable. Why can't we enumerate all programs of size i = 0 in lexicographical order - if any produce string s, that is the Kolmogrov complexity; if not, increment i and iterate? Won't that prove that no program of length < i generates string s?

$\endgroup$

1 Answer 1

4
$\begingroup$

The problem with your approach is that some programs never halt, and it's difficult (indeed, uncomputable) to tell whether they do. You can tell if a program outputs $s$ and halts, but you don't know how much to wait before declaring that the program never halts. However, your approach shows that it is possible to write a program that prints upper bounds on the Kolmogorov complexity of a give string, eventually printing the correct upper bound. This doesn't give you the Kolmogorov complexity since you don't know when the program will have printed its final upper bound.

$\endgroup$
1
  • $\begingroup$ Phenomenal! Grea $\endgroup$ Oct 31, 2014 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.