2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Where did you take this problem? Could you indicate the source? Also are you sure about $ \in$ instead of $\notin$? $\endgroup$
    – fade2black
    Commented Nov 5, 2017 at 9:24

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

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.