# Language of Turing Machines that only accept their own encodings

Is the language $$L = \{\langle M\rangle|L(M)=\{\langle M\rangle\}\}$$ recursive?

I've been trying for hours to find a way to prove or disprove that it is.

My first attempt was to show it wasn't recursive using Rice's theorem but I'm not sure if one can create a Turing machine that only accepts it's own encoding? How would it figure out it's own encoding at run time?

• Try a direct diagonalization. Mar 8, 2022 at 18:20
• Rice's theorem is possible to apply. For the existence of a TM that accepts its own code check this question. Mar 8, 2022 at 20:09

You can reduce K to L:

Let

K = {e | e's Turing machine halts on e}

Let f(x,y) be

f(x,y) = Code of the following machine:

For any input w:

Run y's Turing machine on y.

If w = x, accept. Otherwise reject.

Here by Recursion theorem, We know there is some computable function s which:

f(s(y),y) = s(y)

Also by proof of Recursion theorem, we know that s(y) can be computably constructed from f((which is computable)) and y. So we can compute s(y) from y.

Here by definition of f, we know that if M is the Turing machine encoded by s(y) Then:

L(M) = {s(y)} if and only if y belongs to K.

So we reduced K to L. Since K is not recursive, L is not recursive either.

For your second question about how to construct a Turing machine which only accepts its own code. I refer you to Recursion theorem and the following question:

Understanding Whether a Set is an Index Set

• $L$ does not satisfy 2. Jan 26 at 15:10