1
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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.) $\endgroup$ – starflyer Nov 15 '13 at 4:43
0
$\begingroup$

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?)

$\endgroup$
5
  • $\begingroup$ We would use another TM to read the first part of the merge and check whether x is in H.... But what happens when we look at the complement part of the merge? We know that it can't be enumerated. $\endgroup$ – Heplar Nov 14 '13 at 0:32
  • $\begingroup$ I'm a little lost here. Wouldn't $H\bot H^c$ simply be Σ*? $\endgroup$ – starflyer Nov 15 '13 at 4:51
  • $\begingroup$ @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. $\endgroup$ – hmakholm left over Monica Nov 15 '13 at 11:03
  • $\begingroup$ Ok got it. I was skimming over that part. $\endgroup$ – starflyer Nov 15 '13 at 15:09
  • $\begingroup$ @Heplar: Suppose you keep looking at successive outputs from $T$ until you see either $x\mathtt0$ or $x\mathtt1$ ... $\endgroup$ – hmakholm left over Monica Nov 15 '13 at 16:06

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.