# Is the language $\{f(x)\mid \mbox{$x$is the code of a machine accepting$f(x)$}\}$ recursively enumerable and undecidable?

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.

• 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. – D.W. May 30 '15 at 15:44
• @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.) – Rick Decker May 30 '15 at 15:49
• @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." – David Richerby May 30 '15 at 16:16
• @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!" – 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.

• 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. – babou Jun 2 '15 at 11:17
• @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. – 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.