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

Machines whose languages are their own encoding

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

Problem

Is the language $S = \{\langle M \rangle \mid M \text{ is a Turing Machine and } L(M) = \{\langle M \rangle\}\,\}$ decidable, recognizable and/or co-recognizable?

I tried diagonalization but can only prove that $R = \{\langle M \rangle \mid M \text{ is a Turing Machine and } \langle M \rangle \notin L(M)\}$ is not recognizable, which does not seem to help in this case...

Solution

Using the recursion theorem, for any Turing machine $T$ you can construct a Turing machine $M$ such that on input $\langle M \rangle$, $M$ executes $T$ (on the empty tape), and otherwise $M$ immediately rejects. You can use this to show that $S$ is not decidable. Using the same ideas you can explore its recognizability and co-recognizability.

Context

StackExchange Computer Science Q#50833, answer score: 4

Revisions (0)

No revisions yet.