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.