0
$\begingroup$

My question is this:

Let Y and N be two languages over a fixed alphabet Σ such that both Y and the complement of N are Turing-recognisable.

Prove that if N ⊆ Y , then there exists a decidable language S that splits Y and N, that is: N ⊆ S ⊆ Y.

I already have a theorem which says if a language and its complement are both Turing-recognisable, then the language is decidable. I don't quite know how to apply that to S in this proof though.

Your help is appreciated, thanks!

$\endgroup$
2
$\begingroup$

You have a Turing machine $A$ with

  • If $x\in Y$, then $A$ halts with output Y
  • If $x\notin Y$, then $A$ halts with not Y or does not halt at all

You have a Turing machine $B$ with

  • If $x\notin N$, then $B$ halts with output not N
  • If $x\in N$, then $B$ halts with N or does not halt at all

Now build a Turing machine $C$ that runs $A$ and $B$ on identical input (copies) "in parallel" (how?) and that halts as soon as either of the two components halts. Let the output be S it halts because the $A$-part halts with output Y, and let the output be not S if it halts because the $B$-part halts with output not N. Since $Y\cup \overline N$ covers all possible input, one of the two cases will happen, in particular $C$ will always halt.

$\endgroup$
1
$\begingroup$

Hint: Run recognizers for $Y$ and $N^\complement$ in parallel. If one of them halts, output what it says.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy