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.

  • $\begingroup$ You have only tried rephrase the claim, but that's already not quite correct; you say you only need to show that $R^c \neq \emptyset$ while in fact you need to show that there's a program $\pi$ so that $U(\pi, \_)$ semi-decides $R$. $\endgroup$ – Raphael Dec 12 '14 at 11:38

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.


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.


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.