Define the language
$\qquad R = \{x \in \{0,1\}^\ast \mid C(x) \ge |x| \}$
where $C(x)$ is the Kolmorgorov Complexity of $x$ and $|x|$ denotes the length of $x$.
Prove that $R$ is co-recursively enumerable (co-r.e.).
So far, I have the following:
In order to prove the above, we need to show
$\qquad R^c$ = $\{x \in \{0,1\}^\ast \mid C(x) \lt |x| \}$
is r.e. That is there exists a program $\pi$ such that the univeral TM $U$ with argument $\pi$ equals $x$ and $|\pi| \lt |x|$ (where $U(\pi) = x$ and $|\pi| \lt |x|$).
We start by enumerating all strings in $\{0,1\}^\ast$.
I have no idea where to go from this point onward.