Prove $L$ = $\{\langle M \rangle$ | $M$ is a TM over $\{0,1\}$ and $\langle M \rangle \langle M \rangle \notin \mathcal{L}(M)\}$ is undecidable.

Question

Was stuck on this for a bit so I need to know if I am on the right track.

To show that $L$ is undecidable we will show that $\overline{L}$ is undecidable instead. Suppose $\overline{L}$ is decidable by some decider $R$. We will use $R$ to construct a new TM $S$ such that $S$ decides $A_{TM}$.

We construct $S$ as follows:

• Check that the input is of the form $\langle M,w \rangle$ where $M$ is a TM over $\{0,1\}$ and $w$ is a string.
• Construct a new TM $M_w$ as follows:
  • Input is $x$
  • Erase input $x$ and write the constant string $w$ instead
  • Simulate $M$ on $w$
• Feed $\langle M_w \rangle$ to $R$. If $R$ accepts, accept. If $R$ rejects, reject.

If $w \in \mathcal{L}(M)$ then $M_w$ accepts all strings and therefore also accepts the string $\langle M \rangle \langle M \rangle$. If $w \notin \mathcal{L}(M)$ then $M_w$ accepts nothing. So R($\langle M_w \rangle$) accepts exactly when $M$ accepts $w$, therefore $S$ decides $A_{TM}$. This is a contradiction since $A_{TM}$ is undecidable so $\overline{L}$ must be undecidable which implies that $L$ is undecidable.

Answer 1

Your are correct. This question and the other one reside on Rice's theorem.

There are countably many computable functions and they can be indexed by Godel numbering. So, we denote with $\varphi_n$ the $n$-th computable function. Also, let $\mathcal{PR}$ be the class of all computable (in other words, partial recursive) functions. Finally, we write $\varphi_n(x)\uparrow$ if $\varphi_n$ is not defined on $x$.

Rice's theorem: For any proper ($\mathcal{C}\subsetneq\mathcal{PR}$) and non-empty ($\mathcal{C}\neq\emptyset$) subclass, $\mathcal{C}$, of computable functions, the set $\{n : \varphi_n\in\mathcal{C}\}$ is undecidable.

It turns out that computable functions correspond to turing machines. Each turing machine is a computable function and vice versa. Specifically, for the one direction of the correspondence, we can map each Turing Machine $M$, to a partial recursive function $f_M$ such that $$f_M(x)\uparrow \text{ iff $M$ does not halt on }x\\ f_M(x)=1 \text{ iff $M$ accepts on }x\\ f_M(x)=0 \text{ iff $M$ rejects on }x$$

Then the language of $M$ is $L(M)=f_M^{-1}(1)=\{x: f_M(x)=1\}$.

So, in the machine context, Rice's theorem states that the language $L=\{\langle M\rangle: M\in\mathcal{C}\}$ is decidable if and only if $\mathcal{C}=\emptyset$ or $\mathcal{C}$ is the class of all Turing Machines. In other words, all languages $L=\{\langle M\rangle: M\text{ has a non-trivial property}\}$ are undecidable. Trivial property means $M$ is not a turing machine (case $\mathcal{C}=\emptyset$) or $M$ is a turing machine (case $\mathcal{C}$ is the class of all Turing Machines).

In this exercise, $\mathcal{C}$ is the subclass of all turing machines, $M$, that accept on input $\langle M\rangle\langle M\rangle$. And in the other exercise, $\mathcal{C}$ was the subclass of Turing machines that accept on input $UIUC$. In both exercises, $\mathcal{C}$ is a proper nonempty subclass of turing machines.

The proof for Rice's theorem is an analogue of the proofs of those two exerices. Instead of Turing machines he uses partial recursive functions, but their functionalities are equivalent to the functionalities of the Turing machines used in the solutions.