1
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ Ok so from what I understand $M_w$, you are saying that $M_w$ is a machine with the constant string $UIUC$ written on its tape? $\endgroup$ Commented Feb 13, 2014 at 22:33
  • $\begingroup$ @1337holiday. No, $M_w$ must have somewhere stored the string $w$, so that it substitutes each input with $w$. There is no need to store $UIUC$ in any tape. $\endgroup$
    – frabala
    Commented Feb 13, 2014 at 22:54
  • $\begingroup$ Ok so lets say our input is $<M,w>$ and $w = abc$ just for example, how exactly will you construct $M_w$ and what will its purpose be? $\endgroup$ Commented Feb 13, 2014 at 22:59
  • 1
    $\begingroup$ The construction is quite simple. Try following step by step the answer. $M_{abc}$ is a machine that has entire $M$ stored and also the string $abc$ stored. Say I give input $jklm$ in $M_{abc}$. Then, $M_{abc}$ will substitute $jklm$ with $abc$ and run $M$ on input $abc$ and it will accept iff $M$ accepts. So, whatever input you give to $M_{abc}$ it will always accept, or always reject, depending on whether $M$ accepts or rejects $abc$. $\endgroup$
    – frabala
    Commented Feb 13, 2014 at 23:07
  • $\begingroup$ @1337holiday Hey, I would really appreciate it if you gave me some reputation for my answer. I mean if it was helpful to you... A vote up if not accept...? Only if you feel like to. :) $\endgroup$
    – frabala
    Commented Feb 13, 2014 at 23:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .