2
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

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

I hope this can help you.

$\endgroup$
2
  • 1
    $\begingroup$ $L$ does not satisfy 2. $\endgroup$ Jan 26 at 15:10
  • $\begingroup$ You are right. Thanks for mentioning that. I edit my answer. I hope this one would be correct $\endgroup$ Jan 26 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.