2
$\begingroup$

We are given two Turing machines $M_1$ and $M_2$ and we wish to decide whether the union of the language $L(M_1)$ accepted by $M_1$ with the language $L(M_2)$ accepted by $M_2$ coincides with $\Sigma^*$.

Is this problem undecidable? In other words, is the language $\{ (M_1, M_2) \mid L(M_1) \cup L(M_2) = \Sigma^*\} $ undecidable?

I'm thinking about doing a proof by contradiction and somehow reducing to $E_{TM}$, but not sure where to start.

$\endgroup$
2
  • 1
    $\begingroup$ What are $M_1$ and $M_2$? The question is unclear, please define precisely "the resulting language". And if this is an exercise, please transliterate the exact wording. $\endgroup$ Nov 23, 2021 at 19:34
  • $\begingroup$ I have edited your question. Please check if it matches what you intended to ask. Also it is still unclear what $E_{TM}$ is and how reducing to (and not from) another language would help to prove that your language is undecidable. $\endgroup$
    – Steven
    Nov 23, 2021 at 20:43

1 Answer 1

4
$\begingroup$

Yes, the language $L = \{ (M_1, M_2) \mid L(M_1) \cup L(M_2) = \Sigma^* \}$, where $M_1$ and $M_2$ are Turing machines, is undecidable.

If $L$ were decidable then you would be able to decide if the language accepted by a Turing machine $T$ is $\Sigma^*$ by simply checking whether $(T,T) \in L$.

To see that the problem of deciding whether a given Turing machine $T$ satisfies $L(T) = \Sigma^*$ is undecidable you can reduce from the well-known undecidable problem of deciding whether a given Turing machine $M$ halts on empty input. To do so, it suffices to construct $T$ from $M$ by replacing each transition that halts the machine and rejects with a transition that halts the machine and accepts. Then $M$ halts if and only if $L(T)=\Sigma^*$.

$\endgroup$
1
  • 1
    $\begingroup$ Good job on understanding what the question was! $\endgroup$
    – Nathaniel
    Nov 23, 2021 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.