Show that the set of programs whose Kolmorgorov complexity is smaller than their length is recursively enumerable

Question

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.

Answer 1

Fancy answer

We need to show that the set $$R = \{x \in \{0,1\}^* \mid C(x) < |x|\}$$ is c.e. (allow me to use the new terminology). The defining condition for $R$ is equivalent to $$\exists n, m \in \mathbb{N} \,.\, T(n,0,m) \land U(m) = x \land |n| < |x| \tag{1}$$ where $T$ is Kleene's predicate and $U$ the associated output function. In words, the formula means: there exists a code $n$ such that the $n$-th machine computes $x$ (on input $0$) and the length of $n$ is less than the length of $x$. We are done because (1) is a $\Sigma^0_1$-formula, therefore it defines a c.e. predicate.

Scholium: a $\Sigma^0_1$ formula is a formula of the form $$\exists n \in \mathbb{N} \,.\, \phi(n, x)$$ where $\phi(n,x)$ is a decidable formula. Such a formula determines a c.e. predicate: to semidecide whether it holds for $x$, just run a loop $n = 0, 1, 2, \ldots$ and test for each $n$ whether $\phi(n,x)$ holds. If and when such an $n$ is found, terminate.

Non-fancy answer

In paralell, run all machines described by codes of length less than $|x|$ (there are around $2^{|x|}$ such machines, which is a finite number). If and when one of them stops and produces output $x$, terminate.

Answer 2

An alternative, simple but formal answer is to observe that $\overline{R}$ can be partially enumerated by the following computable function:

$$g(i) = \begin{cases}|\varphi_i(x)| & if~|i| < |\varphi_i(x)| \\ \uparrow & otherwise \end{cases}$$

Here, $\varphi$ is an acceptable enumeration of the partial recursive functions. I leave details to the reader.