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 Answer 1


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.

  • 6
    $\begingroup$ Thanks--so simple and clear. (I think that one is supposed to indicate thanks only with upvote and checking "answered" rather than comments, but sometimes that feels unsatisfying.) $\endgroup$
    – Mars
    Aug 11 at 17:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .