# Decidability of whether $w \in L(M_1) \setminus L(M_2)$

I'm studying for my finals and I came across this question from past exams:

Is the following language decidable? $$L = \{ \langle M_1,M_2,w \rangle \mid w \in L(M_1) \setminus L(M_2) \}.$$

How can I be sure of my answer? Is there any way to know for sure?

• The way we know for sure in mathematics is by proving things. Jan 15 at 11:22

Intuitively, $$L$$ is not decidable as given $$\langle M_1, M_2, w\rangle$$ we need to decide whether
1. $$w\in L(M_1)$$, and
2. $$w\in \overline{L(M_2)}$$.
The first condition smells like deciding the language $$A_{TM} = \{ \langle M, w \rangle: \text{ M accepts w}\}$$, and the second condition smells like deciding $$\overline{A_{TM}}$$. To make sure that the intuition got it right, you need to prove formally undecidability for $$L$$, here is a hint.
Hint: show that there is a reduction from some undecidable language to $$L$$. It is sufficient to capture the hardness of one the above conditions. Thus, to make things simpler, think how you can fix one of the machines $$M_1$$ or $$M_2$$ in the reduction's output, so that one of the conditions holds trivially. I leave the rest to you.