Reducing A$_\text{TM}$ to REGULAR$_\text{TM}$

Question

We can solve A$_\text{TM}$ problem using REGULAR$_\text{TM}$.

Assume $R$ is a Turing machine that decides REGULAR$_\text{TM}$. We construct $S$ to decide A$_\text{TM}$ as follows

On input $\langle M, w \rangle$, where $M$ is a TM and $w$ is a string, $S$ constructs the following TM $M’$

On input $x$:

• if $x$ has the form $0^{n}1^n$, accept;
• If $x$ does not have this form, run $M$ on input $w$ and accept if $M$ accepts $w$”

Run $R$ on input $\langle M’ \rangle$, and output the output of $R$.

Now, $S$ decides A$_\text{TM}$... Contradiction!

But I didn't understand why $M'$ is regular if it accepts $w$. $0^{n}1^n + \text{(a language)}$ is regular?

Thanks in advance.

Answer 1

The trick is to carefully look at the language of the constructed Turing machine $M^\prime$.

• If $M$ accepts $w$, then $L(M^\prime) = \Sigma^*$ (and is thus regular).

  For any input $x$ of $M^\prime$, either

  • $x = 0^n1^n$ (for some $n$), in which case $M^\prime$ accepts $x$, or
  • $x$ is not of this form, and we run $M$ on input $w$, and since $M$ accepts $w$, then $M^\prime$ accepts $x$.

• If $M$ does not accept $w$, then $L (M^\prime) = \{ 0^n1^n : n \geq 0 \}$ (and is thus not regular).

  For any input $x$ of $M^\prime$, either

  • $x = 0^n1^n$ (for some $n$), in which case $M^\prime$ accepts $x$, or
  • $x$ is not of this form, and we run $M$ on input $w$, and since $M$ does not accept $w$, then $M^\prime$ does not accept $x$.

So $L(M^\prime)$ is regular if and only if $M$ accepts $w$. Thus running $R$ on the constructed Turing machine $M^\prime$ will tell us whether or not $M$ accepts $w$.