2
$\begingroup$

If Q1 and Q2 are countably enumerable, then is Q1\Q2 countably enumerable?

I am reading a text where they claim that this is not the case and ask the reader to come up with a counter example.

Can someone give a counter example to the claim that if both Q1 and Q2 are c.e. then so is Q1\Q2?

Since H is semi-decidable and hence also c.e., I was thinking of coming up with examples using it, but no success till now.

$\endgroup$
  • 3
    $\begingroup$ What's "countably enumerable"? Do you mean "recursively enumerable"? $\endgroup$ – xskxzr May 16 '18 at 2:49
  • 3
    $\begingroup$ Try taking $Q1$ to be the full language. $\endgroup$ – chi May 16 '18 at 9:17
  • $\begingroup$ A decision problem is countably enumerable if there is a function f:N->Q that enumerates it and f is computable. Equivalently, Q is countably enumerable if there is a register machine/Turing machine that given any i in N, outputs Qi in Q.so if a problem, is semi decidable, we can just run simulate all machine with inputs 1 to infinity in parallel (one step of a machine at a time), to give an enumeration... $\endgroup$ – Anirudh Gangwal May 16 '18 at 9:41
  • $\begingroup$ @xskxzr yes, the book mentions in older literature it is called recursively enumerable, please excuse me as I'm a beginner and am learning things for the first time $\endgroup$ – Anirudh Gangwal May 16 '18 at 11:13
1
$\begingroup$

First of all, notice that not all c.e. sets have a c.e. complement, i.e. there are c.e. sets like $Q$ such that $Q^c=\mathbb{N}-Q$ is not c.e. In fact the Halting Problem $H$ is such a c.e. set.

To see why $H^c$ is not c.e., notice that if both a set and its complement are semi-decidable, then both are also decidable. And since $H$ is not decidable, then $H^c$ should not be semi-decidable either.

Now for the counter example to your question, let $Q_1 = \mathbb{N}$ and $Q_2 = H$. Then $\mathbb{N} - H = H^c$, is not c.e.


Edit: Explained $H^c$ and added a simpler and more straightforward counter example.

$\endgroup$
  • $\begingroup$ Thanks. Is the complement of H, the looping problem, i.e. does this machine loop? Or we can't make statements such as this? $\endgroup$ – Anirudh Gangwal May 20 '18 at 5:44
  • $\begingroup$ No. What a looping program itself enumerates (or accepts) is just an empty set, which is computable. $H^c$ contains the codes of looping programs, i.e. codes of machines and inputs on which the corresponding machine does not halt. I have edited my answer for better clarity. $\endgroup$ – Beleg May 20 '18 at 10:44

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.