4
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
6
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\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 '13 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$ – David Richerby Dec 14 '13 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 '13 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 '13 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 '13 at 15:02
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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