Why is incomputability weaker than Kolmogorov complexity?

441 Views Asked by At

Abbot et al. "Experimentally probing the algorithmic randomness and incomputability of quantum randomness" remark that "incomputability is a weaker property than Kolmogorov randomness". I understand that a Kolmogorov random infinite sequence is incomputable. The statement implies that there are incomputable sequences that are not Kolmogorov random. Why? (It's difficult for me to imagine what such a sequence would be like. If the answer is complicated, pointers to textbooks or literature at a similar level would be welcome.)

1

There are 1 best solutions below

1
On BEST ANSWER

Take your favorite noncomputable infinite binary sequence $f$ and consider the new sequence $$g:=f(0), 0, f(1), 0, f(2), 0, ...$$ Clearly $g$ is again noncomputable ($f$ and $g$ have the same Turing degree), but $g$ also has lots of "predictable behavior" since every other bit of $g$ is zero. This prevents $g$ from being Kolmogorov random. So, in fact, not only does noncomputability not imply randomness, but every noncomputable sequence has the same Turing degree as a non-random sequence.