0

Prove that $L=\{ \langle M \rangle \;|\; \langle M \rangle \in L \left( M \right) \}$ 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:

ATM ≤M(mapping reducible) M

Find a map : f:-> such that DL doesn't recognize w.<=> 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.

user137481
  • 2,605
user499302
  • 1

1 Answers1

0
ATM(M, w):   
    Construct
    T = "On input x:
         100) if x = <T>
         200)    Run M on w
         300)    if M accepts w
         400)        accept
         500)    else
         600)        reject
        "
if DL accepts T
    accept
else
    reject

Notice that:
$\quad DL$ accepts $T \Rightarrow T \in L$
$\quad\quad\quad\quad\quad\quad\quad \Rightarrow$ we reach line 400
$\quad\quad\quad\quad\quad\quad\;\;\; \Rightarrow M$ accepts w on line 300
$\quad DL$ rejects $T \Rightarrow T \not \in L$
$\quad\quad\quad\quad\quad\quad\;\;\; \Rightarrow M$ rejects/loops on w on line 200

So, $DL$ accepts $T \Rightarrow M$ accepts $w$ whoch would make ATM a decider for $A_{TM}$ which is undecidable.
So, $DL$ cannot be a decider for $L$ and $L$ must be undecidable.

user137481
  • 2,605