# Computability and the Halting Problem

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?

• Again, you probably mean computably enumerable. It's either countable or enumerable, but in the context of your question, you mean computably enumerable (or recognizable is the term that Sipser uses.) – starflyer Nov 15 '13 at 4:43

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?)
• I'm a little lost here. Wouldn't $H\bot H^c$ simply be Σ*? – starflyer Nov 15 '13 at 4:51
• @starflyer: No; the $\bot$ operation appends a 0 to each string from $H$ and an 1 to each string from $H^c$. So when you get an output from the $H\bot H^c$ enumeration you can see which of the sets it came from. – hmakholm left over Monica Nov 15 '13 at 11:03
• @Heplar: Suppose you keep looking at successive outputs from $T$ until you see either $x\mathtt0$ or $x\mathtt1$ ... – hmakholm left over Monica Nov 15 '13 at 16:06