Where does the input x in Turing Machine subroutines come from in solving reductions to undecidable problems?

Question

I'm taking an introduction to computation theory class and we went over the chapter on undecidable problems and proving undecidability through reductions. I can't seem to grasp some of the simplest problems when it comes to reduction however.

For example there is the problem $\mbox{REGULAR}_{TM} = \{ \langle M \rangle \mid M\mbox{ is a Turing Machine and }L(M)\mbox{ is a regular language}\}$

Most of the time the answers involve creating your own auxiliary Turing Machine. For this example, my book decides to reduce from $A_{TM}$ my book uses $M_{aux}$. I show what $M_{aux}$ looks like within the decider $S$ for $A_{TM}$ they formulated ($R$ is the decider for $\mbox{REGULAR}_{TM}$):

$S = $ "On input $\langle M , w \rangle$, where $M$ is a TM and $w$ is a string:

1. Construct the following TM $M_{aux}$:

   $M_{aux}$: "On input $x$:
   

   1. If $x$ has the form $0^n1^n$, then accept.
   2. If $x$ does not have this form, run $M$ on input $w$ and accept if $M$ accepts $w$."

2. Run $R$ to on $\langle M_{aux} \rangle$.

3. If $R$ accepts, accept. If $R$ rejects, reject."

I don't really understand where $x$ comes from and how $M_{aux}$ uses $x$. According to the book, $M_{aux}$ works by automatically accepting all strings in $\{0^n1^n\mid n \ge 0\}$. If $M$ accepts $w$, $M_{aux}$ accepts all other strings. But what if $M$ doesn't accept $w$ in the second step? In that case it looks like $M_{aux}$ would reject. What happens then?

My main problem is just that I don't understand how $M_{aux}$ runs and how the decider for $R$ uses it. I've looked over many other examples and I understand how to actually create proofs like this, but what I don't understand is the subroutine machine that they create, like $S$ does.

Answer 1

The point is that the behavior of $M_{\rm aux}$ depends only on what $M$ does to $w$:

• If $M$ accepts $w$, then the language $M_{\rm aux}$ accepts is regular (namely everything).
• If $M$ rejects $w$ (such as if it doesn't terminate), then the language $M_{\rm aux}$ accepts is not regular (namely $\{0^n1^n\}$ which is easily shown not to be regular, for example by the Myhill-Nerode theorem).

The input $x$ doesn't come from anywhere, because $M_{\rm aux}$ is never actually run -- we're just feeding it to $R$ to be analyzed, in order that $R$ can tell us which of the two above cases we're in.

It's not particularly important that the two languages $M_{\rm aux}$ may recognize are precisely $0^n1^n$ and $\{0,1\}^*$ -- the important thing is that they ought to be classified differently by $R$, and therefore we can use $R$ (if it works as assumed) to learn things about $M$'s behavior of $w$ that we already know we can't know in general.