# Prove that $L=\{x\mid K(x) \leq |x|-c\}$ is recognizable, where $x \in \{0,1\}^*$

Basically I want to prove that the set of all c-compressible binary strings is recognizable.

My goal is to construct a turing machine $N$ such that, given an input string $x$, $N$ accepts $x$ if there exist a turing machine $M$ and a string $s$ such that $M(s) = x$, and $|\langle M \rangle|+|s| \leq |x|-c$. Since both $|\langle M \rangle|$ and $|s|$ are bounded by $|x|$, there are only finitely many $M$ and $s$ to run through, and the output of each $M(s)$ is either $x$ or not $x$, hence the algorithm halts in finite time, and so $N$ is a decider for $L$.

But this is clearly not the case because $L$ is not co-recognizable. Where is the flaw?

• Hint: you should run (simulate) every $M, |M| < |x|-c$ for a finite number of steps: $t = 1,2,3,...$ (a so-called "dovetailed simulation"), if exists $M'$ such that $U( M' )=x$ then your dovetailed simulation will halt for some $t_i$ – Vor Jun 7 '17 at 13:39

The flaw in your argument is that Turing machines don't always halt. However, if a Turing machine does halt and prints $x$, then it gives you an upper bound on the Kolmogorov complexity.
• I see, since $M$ does not necessarily halt on $s$ even if both $|\langle M \rangle|$ and $|s|$ are finite. What about the rest of my argument? Do they work? – Sid Caroline Jun 7 '17 at 13:23