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?

  • $\begingroup$ 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$ $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – Sid Caroline Jun 7 '17 at 13:23
  • $\begingroup$ If one part is wrong, the entire argument fails. $\endgroup$ – Yuval Filmus Jun 7 '17 at 17:36

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.