2
$\begingroup$

I just looked into Kolmogorov complexity today and it appears to me that for a binary string of length $1$ (ex. '$0$') the Kolmogorov complexity must be $0$.

It follows that Kolmogorov complexity may not be computable in general but there must be some strings for which Kolmogorov complexity is trivially computed.

Is this correct?

$\endgroup$
  • $\begingroup$ Kolmogorov Complexity deals with algorithms. You can't have an algorithm of length 1. $\endgroup$ – theDoctor Jun 14 '16 at 13:45
0
$\begingroup$

One could enumerate all the algorithms (the set they form is countable) in a given language in some order of increasing length, and the strings that are outputted by these algorithms then have known Kolmogorov complexity. In general, there is no way to compute the Kolmogorov complexity of a given string. Of course, one runs into the problem of non-terminating algorithms, which is itself an undecidable property, so this is not sensible in practise.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy