Decidability/Undecidability Question

524 Views Asked by At

Could someone please help me with this question? I'm really having a hard time understanding reductions and decidability.

Prove that the language $$L = \{\langle M,N \rangle \mid M,N\text{ are Turing machines and }L(M) \subseteq L(N)\}$$ is undecidable.

How do I prove this question?

1

There are 1 best solutions below

0
On

The details of the argument depend on what you have proved already. Ultimately, most of the negative results are proved by showing that if there were a Turing machine that could do a certain task, then the TM could be modified to solve the Halting Problem.

From your comment, you have already shown that there is no TM that will recognize when a language is empty. In that case, you can answer the current question quickly.

If there was a TM for determining in general whether $L(M)\subseteq L(N)$, then by feeding into it an arbitrary Turing machine $M$ and a simple concrete TM $N_0$ that accepts only the empty language, you would have a TM for determining whether the language accepted by a TM $M$ is empty. For if $N_0$ is our fixed concrete TM for the empty language, then $L(M)\subseteq L(N_0)$ if and only if $L(M)$ is empty.