Computability and the Halting Problem

Question

This is a branch of another problem that I had asked earlier (and was answered). Found here

Let the "merge" of two languages L1,L2⊂{0,1}* be:

L1⊥L2 = {x0 | x∈L1}∪{y1|y∈L2}

Given the diagonal halting problem H, and its complement H', is H$\bot$H' c.e or co-c.e? (Countably enumerable/Recursively enumerable)

I don't believe it can be either one. H itself is countably enumerable because all of the halting problems themselves (within H) can be enumerated by listing all of the possible programs with their possible inputs.

However the complement isn't because the halting problem itself isn't solvable.

Which means both the merge of these two problems and the complement of the merge can't be c.e or co-c.e because H' isn't c.e.

Am I on the right track at all? How could I prove this?

Answer 1

Yes, you're on the right track.

In order to make your informal reasoning into an actual proof that $H\bot H^c$ is not r.e., you could say something like

Assume for a contradiction that $H\bot H^c$ is r.e. This means that there is a Turing machine $T$ that enumerates $H\bot H^c$. Now suppose we're given $x$ and want to discover whether $x\in H$. We could then ... (can you take it from here?)