4
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ how do you verify that $D(a) = x$ in finite time? $\endgroup$ 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$ Jul 1 '13 at 3:52
  • $\begingroup$ It is by a definition of a description mapping. $\endgroup$ 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$ Jul 1 '13 at 4:19
2
$\begingroup$

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.

$\endgroup$
2
  • $\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$ 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.