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.)
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Aug 11 at 17:46
-
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$– MarsAug 11 at 17:49