2
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\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, 2017 at 13:39

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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, 2017 at 13:23
  • $\begingroup$ If one part is wrong, the entire argument fails. $\endgroup$
    – Yuval Filmus
    Jun 7, 2017 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.