HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Decide the set of all Turing machines with $L(M)=\left\{\langle M\rangle\right\}$

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
lefttheallwithlanglerangledecidemachinesturingset

Problem

How can I prove that the language $L=\left\{\langle M\rangle\mid L(M)=\left\{\langle M\rangle\right\}\right\}$ is not decidable?

When trying to use a diagonal argument, I cannot conclude from $L(M)\ne\left\{\langle M\rangle\right\}$ that $\langle M\rangle\not\in L(M)$.

Also, it seems that I cannot apply Rice's theorem because I can't say anything about the machines' encodings $\langle M\rangle$ in the definition of the set $\mathcal{S}$.

Is there an easy reduction to a known undecidable language?

Solution

The recursion theorem states that a Turing machine can get its own description on to its tape. In fact, there is a simple reduction from the acceptance problem (ATM) to this problem.

Assume $L$ is decidable. Suppose I am asked whether a TM $M$ accepts $w$. I will construct a machine $M'$ which on input $x$ checks if $x=\langle M' \rangle$. If it is not $\langle M' \rangle$ it simply rejects $x$. Otherwise it simulates $M$ on $w$, and if $M$ accepts $w$ then $M'$ accepts $x$. So $L(M') = \{ \langle M' \rangle \}$ iff $M$ accepts $w$. Hence we can pass this $M'$ as input to the decider $L$ and obtain answer for "$M$ accepts $w$?". But we know that ATM is undecidable, hence $L$ must be undecidable.

Context

StackExchange Computer Science Q#66560, answer score: 4

Revisions (0)

No revisions yet.