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$ – Sasho Nikolov Jul 1 '13 at 3:50
  • $\begingroup$ If it was not finite, then the output would be indeterminate but $D$ maps every description to some object. $\endgroup$ – Dávid Natingga Jul 1 '13 at 3:52
  • $\begingroup$ It is by a definition of a description mapping. $\endgroup$ – Dávid Natingga Jul 1 '13 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$ – Sasho Nikolov Jul 1 '13 at 4:19

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.

| cite | improve this answer | |
  • $\begingroup$ Isn't iterating over all strings of length $|x|-1$ also not effective? $\endgroup$ – MarkG Feb 23 '15 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$ – Sasho Nikolov Feb 23 '15 at 23:52

Your Answer

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

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