Prove that a given language is not recursively enumerable.

Question

I'm kind of stuck in this question, a have an idea of what to do, but I cannot get a consistent proof:

So it is asking:

Let $B$ be recursively enumerable but not recursive, and let $C = \{\text{0w0 | w does not belong to B}\}$. Show that $C$ is not recursively enumerable.

I started by supposing $C$ to be RE, therefore, that means that $!B$ would also be RE.

I said that if we're given a Turing Machine $Mc$ and it recognises the language $L(Mc) = C$ ... Then, we want to find another Turing Machine $N$ such that $L(N) = !B$...

But there, I don't know what else to do.

Thank you all!

Answer 1

You don't need to find N. Since B is recursively enumerable, there is a machine Mb which enumerates its members. Construct from Mb and Mc a machine which generates members of B and C 'simultaneously' [here you have to simulate interleaved execution - one step of Mb, one step of Mc, repeat...]. For any input string w, eventually either Mb will generate w - hence w is in B - or Mc will generate 0w0 - hence w is not in B. Since it must do one or the other, this machine halts on all inputs. That makes B recursive, contrary to assumption. Hence Mc cannot exist, i.e C is not R.E.