This is text of an exercise I am working on:

Given a binary encoding scheme for the set of the deterministic Turing machines with alphabet $\{0,1\}$ and a bijective and computable function $f: \{0,1\}^* \rightarrow \{0,1\}^*$, prove that the language $$L=\{f(x)\mid \mbox{$x$ is an encoding of a machine that accepts $f(x)$}\}$$ is recursively enumerable and undecidable.

I don't know how to prove it, and I don't know where to start.

  • 1
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. Just copy-pasting an exercise from a textbook is not a suitable question for this site. $\endgroup$ – D.W. May 30 '15 at 15:44
  • 1
    $\begingroup$ @D.W. The OP said s/he had no idea where to start. Seems like a pretty good answer to "What did you try?" (Yes, I know this is a minority position on my part.) $\endgroup$ – Rick Decker May 30 '15 at 15:49
  • 2
    $\begingroup$ @RickDecker "I tried looking at the definitions and theorems X, Y and Z but I couldn't see how to use any of that" seems like a much better answer than something that's indistinguishable from "I didn't try." $\endgroup$ – David Richerby May 30 '15 at 16:16
  • 1
    $\begingroup$ @RickDecker Also, the answer then should be, "If your course was designed at least reasonably well, you should know where to start. Review the material!" $\endgroup$ – Raphael Jun 1 '15 at 10:54

Let $L_f = \{f(x)\mid x \text{ is the encoding of a TM }X\land X\text{ accepts }f(x)\}$

We'll make use of a

Lemma. If $f:\{0, 1\}^*\rightarrow \{0, 1\}^*$ is a computable bijection, then so is $f^{-1}$.

Proof hint. Obviously, $f^{-1}$ is a bijection, since $f$ is. Then use dovetailing to construct a TM that for any input string $y$ returns the (unique) $x$ for which $f(x)=y$.

I. $L_f$ is r.e..

Construct a recognizer $R$ that will accept all and only strings $y\in L_f$ as follows

R(y) =
   compute x such that f(x) = y     // using the Lemma above
   if x is the encoding of a TM, X  // obviously possible to check
      simulate X on input y         // obviously can do this, too
      if X accepts y
         return accept

II. $L_f$ is undecidible.

Suppose, to the contrary, that there was a decider $D_f$ for $L_f$. Define another (decider) TM, $E_f$, to do the "opposite" of $D_f$, i.e., $E_f$ accepts a string if $D_f$ rejects and $E_f$ rejects a string if $D_f$ accepts it. Then let $z=f(\langle E_f\rangle)$.

If $z\in L_f$, then $E_f$ accepts $z$ by the definition of $L_f$ and so by the definition of $E_f$, $D_f$ rejects $z$ and so $z\notin L_f$, a contradiction. Similarly, we can show that, $z\notin L_f\Rightarrow z\in L_f$, another contradiction, so $L_f$ must be undecidable.

| cite | improve this answer | |
  • $\begingroup$ Thanks for your comment (now deleted?). Actually I have been wondering whether the fact that composing a computable bijection with a Gödel enumeration gives a new Gödel enumeration is a standard theorem known to student. It seems so basic that it should be, but I do not know. $\endgroup$ – babou Jun 2 '15 at 11:17
  • $\begingroup$ @babou. The Powers that Be deleted my comment. I agree that this "composition theorem" does seem basic. I can't, of course, speak for all students, but I can say that it comes as a surprise (at first) to many of mine. $\endgroup$ – Rick Decker Jun 2 '15 at 13:30

Using formal notations rather than words would make your life easier. Since you have a binary encoding of Turing Machines (TM), you should use a formal notation for it.

For example you can give it a name, say $g$. Then an encoding $x$ of a TM $M$ can be written $x=g(M)$, or if you want to use the common angle bracket notation: $x=\langle_g M\rangle_g$. Note that I keep $g$ as a subscript of the angle brackets, so that I can distinguish different binary encodings of Turing Machines.

Now, if $g$ is a binary encoding scheme for TMs, then its composition $h=f\circ g$ with a bijective and computable function $f$ (from binary numbers to binary numbers) is also a binary encoding scheme for TMs, such that (using the various possible notations) $h(M)=f(g(M))=\langle_h M\rangle_h=f(\langle_g M\rangle_g)$.

Now you can rewrite the definition of $L$ using this new binary encoding scheme: .$$\begin{align} L&=\{f(x)\mid \mbox{$x$ is an encoding of a machine that accepts $f(x)$}\}\\ &=\{f(x)\mid \mbox{$x=\langle_g M\rangle_g$ and $M$ accepts $f(\langle_g M\rangle_g)$}\} \\ &=\{f(\langle_g M\rangle_g)\mid \mbox{$M$ accepts $f(\langle_g M\rangle_g)$}\}\\ &=\{\langle_h M\rangle_h\mid \mbox{$M$ accepts $\langle_h M\rangle_h$}\} \end{align}$$

It is now easy to see that L is recursively enumerable, since for any value $x$, we can test whether it is in $L$ by running the machine $M$ such that $x=\langle_h M\rangle_h$ with input $x$, which does terminate when $x\in L$.

However, $L$ is not decidable. The proof goes by contradiction. We first suppose that $L$ is decidable. Thus its complement $\overline L$ is also decidable, and is recognized by a Turing machine $\overline M$

If $\overline M$ accepts $\langle_h \overline M\rangle_h$, then $\langle_h \overline M\rangle_h$ is in $\overline L$, the language that $\overline M$ recognizes by definition. But this implies, by definition of $\overline L$ that $\overline M$ does not accept $\langle_h \overline M\rangle_h$.

But if $\overline M$ does not accept $\langle_h \overline M\rangle_h$, then $\langle_h\overline M\rangle_h\notin L$ by definition of $L$. Thus $\langle_h\overline M\rangle_h\in\overline L$. Hence since $\overline M$ recognizes $\overline L$, $\overline M$ must accept $\langle_h \overline M\rangle_h$.

In both cases we have a contradiction. So the hypothesis that $L$ is decidable cannot hold.

| cite | improve this answer | |

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.