I am reading Kolmogorov Complexity by Li and Vitányi:

"Let $x$ be a finite binary string. We write '$x$ is random' if the shortest binary description of $x$ with respect to the optimal specification method $D_0$ has length at least $x$." By length $x$ I understand the natural number that the binary string maps to canonically.

[proof which I do not understand follows]

"This shows that although most strings are random, it is impossible to effectively prove them random."

However, I am able to produce a counterexample and can find a proof that $x$ is random effectively (there is an algorithm). Iterate over all the words of size up to $x-1$ of a description language. If you find a description $\alpha_x$ such that $D_0(\alpha_x)=x$ ($\alpha_x$ describes $x$) then terminate with verdict that $x$ is not random. If you exhaust all the words of length $<x$(there are finitely many since $x$ is finite so the program halts) and none of them describes $x$ and then terminate with result that $x$ is random.

What is wrong in my counterexample?

  • $\begingroup$ how do you verify that $D(a) = x$ in finite time? $\endgroup$ Jul 1, 2013 at 3:50
  • $\begingroup$ If it was not finite, then the output would be indeterminate but $D$ maps every description to some object. $\endgroup$ Jul 1, 2013 at 3:52
  • $\begingroup$ It is by a definition of a description mapping. $\endgroup$ Jul 1, 2013 at 4:01
  • $\begingroup$ You could just read further into Li and Vitanyi's book for the details, but maybe this will help: scholarpedia.org/article/… $\endgroup$ Jul 1, 2013 at 4:19

1 Answer 1


The catch is that $D_0$ is only a partial recursive function and it may not be possible to verify that $D_0(\alpha) = x$ in finite time. There is no way around that because $D_0$ must be universal, and there is no way a machine implementing it would halt on every input, because not every Turing machine halts on every input.

  • $\begingroup$ Isn't iterating over all strings of length $|x|-1$ also not effective? $\endgroup$
    – MarkG
    Feb 23, 2015 at 21:56
  • $\begingroup$ @MarkG There is only a finite number of them, so that's not a problem. It's not efficient, but that's not a requirement. $\endgroup$ Feb 23, 2015 at 23:52

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.