Skip to main content
Computer Science

Return to Question

Post Closed as "Duplicate" by John L., Evil, David Richerby, Yuval Filmus turing-machines
added 18 characters in body; edited title
Source Link
Yuval Filmus
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

Is the Decidability of language that containsof TMs which accept only their Gödelnumber decidable?Gödel number

I tryam trying to proofprove that $L = \{\langle M \rangle \mid L(M) = \{\langle M \rangle \}\}$ is undecidable, where $\langle M \rangle$ is the code of the TM M$M$, and $L(M)$ the recognized language recognized by $M$.

I think I can't use rice'sRice's theorem, so I tried to find a reduction. The halteproblemhalting problem for example does not helpedhelp me in this case. Do you have an Ideaany idea how to proofprove it?

Is the language that contains TMs which accept only their Gödelnumber decidable?

I try to proof that $L = \{\langle M \rangle \mid L(M) = \{\langle M \rangle \}\}$ is undecidable, where $\langle M \rangle$ is the code of the TM M and $L(M)$ the recognized language.

I think I can't use rice's theorem, so I tried to find a reduction. The halteproblem for example does not helped me in this case. Do you have an Idea how to proof it?

Decidability of language of TMs which accept only their Gödel number

I am trying to prove that $L = \{\langle M \rangle \mid L(M) = \{\langle M \rangle \}\}$ is undecidable, where $\langle M \rangle$ is the code of the TM $M$, and $L(M)$ the language recognized by $M$.

I think I can't use Rice's theorem, so I tried to find a reduction. The halting problem for example does not help me in this case. Do you have any idea how to prove it?

Source Link
Marc
Marc
  • 223
  • 1
  • 6

Is the language that contains TMs which accept only their Gödelnumber decidable?

I try to proof that $L = \{\langle M \rangle \mid L(M) = \{\langle M \rangle \}\}$ is undecidable, where $\langle M \rangle$ is the code of the TM M and $L(M)$ the recognized language.

I think I can't use rice's theorem, so I tried to find a reduction. The halteproblem for example does not helped me in this case. Do you have an Idea how to proof it?