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

Why is $L = \{ \langle M \rangle : L(M) = \{ \langle M \rangle \} \}$ not Turing-recognizable?

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

Problem

In other words, $L$ is the language of Turing machines that recognize the language consisting of only themselves.

Why is $L$ not Turing-recognizable? $L$ is clearly not decidable by Rice's Theorem, but how do I go one step further and also prove that no machine can enumerate $L$?

Solution

Given a Turing machine $T$, use the recursion theorem to construct a Turing machine $T'$ that halts if its input $x$ is $\langle T' \rangle$, runs $T$ on $x$ if $x \langle T' \rangle$. If you could recursively enumerate $L$, then you could use this reduction to recursively enumerate all machines that never halt.

Context

StackExchange Computer Science Q#7469, answer score: 5

Revisions (0)

No revisions yet.