Skip to main content
added 2 characters in body
Source Link
fade2black
  • 9.9k
  • 2
  • 25
  • 36

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)$ meansdenotes 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.

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)$ means 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.

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.

Source Link
fade2black
  • 9.9k
  • 2
  • 25
  • 36

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)$ means 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.