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

How can I show that RC 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 RC is Co-re

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

  • 1
    $\begingroup$ Have you tried proving it yourself? Have you looked into Kum96? $\endgroup$ – Raphael Nov 23 '15 at 19:24
  • $\begingroup$ What's "Kum96"? $\endgroup$ – David Richerby Nov 23 '15 at 20:17
  • $\begingroup$ @DavidRicherby, I would guess it likely is a reference to some other paper, from the paper linked in the question -- it is mentioned in the question. $\endgroup$ – D.W. Nov 23 '15 at 20:56
  • $\begingroup$ one easy way to see that is that a string is compressible (or not algorithmicaly random, by defintion) if it is an output of a turing machine (=> computable) else it is algorithmicaly random (i.e incmpressible, non-computable) $\endgroup$ – Nikos M. Nov 26 '15 at 7:31

We want to show $\overline{R_c}\in RE$.

$\overline{R_c}=\left\{x|\exists M\hspace{1mm} s.t. \hspace{1mm} M(\epsilon)=x,|\langle M\rangle|<|x| \right\}$, i.e. $x$ is not a Kolmogorov-random string if there exists a Turing machine which outputs $x$ (say, when initialized with blank input), with description $\langle M\rangle$ shorter than $|x|$.

Given $x$, run all the Turing machines $M$ with description $|\langle M\rangle|<|x|$ with empty input $\epsilon$, simultaneously (i.e. dont execute any machine for $i+1$ steps before executing all of them for $i$ steps). This is possible since the set of all Turing machines of length $\le |x|$ is finite. If one of the machines halts and outputs $x$, accept, otherwise keep running. If all the machines halted with output different then $x$, reject.

Clearly if $x\in \overline{R_c}$ then our machine accepts, otherwise it either rejects or doesn't halt (which is the case if none of the machines outputs $x$ after some finite number of steps, and at least one of them doesn't halt).


Not only is the set of incompressible strings unrecognizable, no infinite set comprising of incompressible strings is Turing recognizable. Let's assume we could enumerate an infinite set of incompressible strings. Let the enumerator be $E$. Built a Turing machine $M$ ( $M$ disregards its input ) which first obtains its own description $\langle M \rangle $ by recursion theorem. Then it runs the enumerator $E$ and while enumerating the incompressible strings when it sees a string $s$ which is sufficiently longer than $\langle M \rangle $ ( sufficiently long depending on your method of encoding ), then $M$ prints $s$ and halts. This leads to a contradiction as $s$ turns out to be compressible, as it is outputted by $M$ where $\langle M \rangle << |s|$.

I misread the question,sorry for that. Anyways as Ariel has proved the set of incompressible strings is co-recognizable. And I have shown that the set is not recognizable, which also tells us that the set is not decidable.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.