Proving a string is random

Question

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?

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.