set of Kolmogorov-random strings is co-re

Question

given R_C = {x : C(x) ≥ |x|} is a set of Kolmogorov-random strings.

How can I show that R_C is co-re

I have been reading this paper What Can be Efficiently Reduced to the Kolmogorov-Random Strings? which just says that we know that by Kum96 we know that R_C is Co-re

I was not able to find the proof of how that is proved

Answer 1

There is a procedure to enumerate $\{ x : C(x) \lt \vert x \vert \}$, the set of all strings with descriptions shorter than themselves: evaluate every description (in parallel) to see what string it describes, and output that string if it is longer than its description. One way to do this is: on time step $t = 2^k \cdot (2 \cdot x + 1)$, spend a unit of time evaluating the $k^{th}$ description. So this set is recursively enumerable and therefore its complement $R_c$ is in co-RE.