# Proving a string is random

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?

• how do you verify that $D(a) = x$ in finite time? Jul 1 '13 at 3:50
• If it was not finite, then the output would be indeterminate but $D$ maps every description to some object. Jul 1 '13 at 3:52
• It is by a definition of a description mapping. Jul 1 '13 at 4:01
• You could just read further into Li and Vitanyi's book for the details, but maybe this will help: scholarpedia.org/article/… 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.
• Isn't iterating over all strings of length $|x|-1$ also not effective? Feb 23 '15 at 21:56