Is the set $S$ = $\lbrace M \mid M \text{ is a Turing machine and }L(M)=\lbrace \langle M\rangle\rbrace\rbrace$ empty?

In other words is there a Turing machine $M$ that only accepts its own encoding? What about a Turing machine that rejects only its own encoding?


2 Answers 2


The answer is yes.

See Kleene's second recursion theorem: for any partial recursive function $Q(x,y)$ there is an index $p$ such that $\varphi_p \simeq \lambda y.Q(p,y)$.

Suppose that $M$ is a Turing machine that on input $\langle x,y \rangle$ accepts if and only if $x=y$; then, by the above theorem, exists $M'$ such that $M'(\langle y \rangle) = M(\langle M' , y \rangle)$ and we have $L(M') = \{ \langle M' \rangle \}$.

P.S. you can find a very clear proof of the recursion theorem in Chapter 6 of the M. Sipser's book "Introduction to the theory of computation".

  • $\begingroup$ yes but there are multiple/infinite TMs/associated encodings that accept the same language & it is undecidable to check for equivalence.... $\endgroup$
    – vzn
    Dec 14, 2013 at 21:48
  • $\begingroup$ @vzn So? Vor has shown that a Turing machine exists with the required property. His proof is non-constructive but why is that a problem? $\endgroup$ Dec 14, 2013 at 22:10
  • $\begingroup$ is there some way to sketch out how it avoids the TM equivalence/multiple encodings issue? seems there is some room for slightly different interpretation of the question... would say its a subtlety that deserves some attn... $\endgroup$
    – vzn
    Dec 15, 2013 at 0:51
  • 1
    $\begingroup$ @MahmoudA.: it's not annoying, but I don't understand what you mean with "what happens with your programming example if we give the program an encoding in any different programming language". I didn't fixed the encoding function, I simply applied the Kleene's recursion theorem; but if you know any programming language it is easy to build a simple program that prints itself; then you can modify it to store its description in a variable instead of printing it and comparing it to the input. $\endgroup$
    – Vor
    Dec 15, 2013 at 14:58
  • 3
    $\begingroup$ For example, in Java: public class R{public static void main(String[] a){byte c[]={34};String x=new String(c);String s="public class R{public static void main(String[] a){byte c[]={34};String x=new String(c);String s=;System.out.println(s.substring(0,97)+x+s+x+s.substring(97));}}";System.out.println(s.substring(0,97)+x+s+x+s.substring(97));}} $\endgroup$
    – Vor
    Dec 15, 2013 at 15:02

Yes. For the trivial reason that we can choose the coding to have the property we want. (Note that there is no unique way of coding.) For example, let $\langle - \rangle$ be any coding function for Turing machines and let $M_0$ be some Turing machine with $L(M_0) = \{0\}$. Now, let $$\langle M\rangle' = \begin{cases} 0 & \text{ if } M=M_0 \\ \langle M \rangle+1 &\text{ if } \langle M\rangle < \langle M_0\rangle \\ \langle M \rangle &\text{ otherwise.} \end{cases} $$

We have $L(M_0) = \{\langle M_0\rangle'\}$, as required.


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.