# Prove that { ⟨M⟩ ∣ ⟨M⟩ ∉ L(M) } is undecidable

Prove that $L = \{\langle M \rangle \mid \langle M \rangle \notin L(M)\}$ is undecidable. Hint: If there were a decider TM DL for L, what would happen if we gave DL its own description as input?

Here's what I've got so far:

$\mathrm{ATM} ≤_M M$ (with $\leq_M$ being mapping reducible)

Find a map : $f: \langle M \rangle \to \langle DL \rangle$ such that DL doesn't recognize w if and only of x is M's own description.

DL(w):
if w != description:
run on M(w)
if M(w) accepts:
return accept


I couldn't figure out how to relate DL to ATM to prove that L is unrecognizable. My answer might be partially wrong, but I tried my best. Any help is appreciated.

• Where did you take this problem? Could you indicate the source? Also are you sure about $\in$ instead of $\notin$? – fade2black Nov 5 '17 at 9:24

You do not need to reduce $ATM$ to $L$. As it hints, Let $L$ is recognized by a TM $M_L$, and note that $L = L(M_L)$ ($L(M_L)$ denotes the language recognized by $M_L$). Then you have the following contradictions $$\langle M_L \rangle \in L \implies \langle M_L \rangle \notin L(M_L) \implies \langle M_L \rangle \notin L$$ and $$\langle M_L \rangle \notin L \implies \langle M_L \rangle \in L(M_L) \implies \langle M_L \rangle \in L$$ This completes the proof.