# Can I construct a Turing machine that accepts only its own encoding?

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?

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".

• yes but there are multiple/infinite TMs/associated encodings that accept the same language & it is undecidable to check for equivalence.... – vzn Dec 14 '13 at 21:48
• @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? – David Richerby Dec 14 '13 at 22:10
• 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... – vzn Dec 15 '13 at 0:51
• @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. – Vor Dec 15 '13 at 14:58
• 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));}} – Vor Dec 15 '13 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.