Let $L_{UIUC}$ = $\{ \langle M \rangle$ : $L(M)$ contains the string $UIUC\}$. Prove that $L_{UIUC}$ is undecidable.

Question

Been stumped as to why the following proof works.

Note: I have taken this proof directly from here.

Proof by reduction from $A_{TM}$. Suppose that $L_{UIUC}$ were decidable and let $R$ be a Turing machine deciding it. We use $R$ to construct a Turing machine deciding $A_{TM}$. $S$ is constructed as follows:

• Input is $\langle M,w \rangle$, where $M$ is the code for a Turing Machine and $w$ is a string.
• Construct code for a new Turing machine $\langle M_w \rangle$ as follows:
  • Input is a string $x$.
  • Erase the input $x$ and replace it with the constant string $w$.
  • Simulate $M$ on $w$.
• Feed $\langle M_w \rangle$ to $R$. If $R$ accepts, accept. If $R$ rejects, reject.

If $M$ accepts $w$, the language of $M_w$ contains all strings and, thus, the string $UIUC$. If $M$ doesn't accept $w$, the language of $M_w$ is the empty set and, thus, doesn't contain the string $UIUC$. So $R(\langle M_w \rangle)$ accepts exactly when $M$ accepts $w$. Thus, $S$ decides $A_{TM}$.

---

What I am confused about is how they are constructing this new machine $M_w$. What is the input $x$? What is it being replaced with? And finally how are they arriving at the conclusion that if $M$ accepts $w$, the language of $M_w$ contains all strings?

If someone can explain these that would be great, more of a visual learner so if someone can show an example that would be much better.

Answer 1

You assume $L_{UIUC}$ is decidable, so $R$ is the machine that decides this language. Then, with the help of $R$, you construct a machine $S$ that can decide on $A_{TM}$. But it's a fact that $A_{TM}$ is undecidable, so you get a contradiction.

The construction of $S$ is as follows.

• Input is a pair of a turing machine and a string, $\langle M,w\rangle$.

• Process is as follows:

  • Create a turing machine $\langle M_{w}\rangle$ such, that

    if $w\in L(M)$

    then $\forall x, x\in L(\langle M_{w}\rangle)$

    else $\forall x, x\notin L(\langle M_{w}\rangle)$

    Explanation on how $\langle M_{w}\rangle$ works: Input of $\langle M_{w}\rangle$ can be any string $x$. $\langle M_{w}\rangle$ will accept $x$ only if $M$ accepts $w$. Since, $x$ is a variable, but $w$ is fixed, $\langle M_{w}\rangle$ will accept all $x$ if $w\in L(M)$ and won't accept any $x$ if $w\notin L(M)$.

  • After creating $\langle M_{w}\rangle$, feed it to $R$. If $R$ accepts, accept. Else, reject.

    Explanation on how $R$ works: $R$, with input a turing machine $T$, is the turing machine that decides if string $UIUC$ is accepted by $T$. When $T=\langle M_{w}\rangle$, there are only two cases. Because of the construction of $\langle M_{w}\rangle$, it will either accept all strings (so $UIUC$, too), or none.

Therefore, $S$ accepts when $R$ does. And $R$ accepts when $UIUC\in L(\langle M_{w}\rangle)$, which happens only if $L(\langle M_{w}\rangle)=\Sigma^*$ ($\Sigma$ is the alphabet of the language and $*$ the Kleene star), which again happens only if $w\in L(M)$.

So, $S$ with input $\langle M,w\rangle$, accepts iff $w\in L(M)$. But this is deciding $A_{TM}$, which is undecidable.