# Undecidability of REGULAR_TM (Detail within Proof)

I'm reading through Sipser's Intro to the Theory of Computation for a class, and I'm having trouble understanding one of the examples in the book.

The example shows how $REGULAR_{TM}$, defined as the problem of determining if a Turing machine recognizes a regular language, is undecidable. The way they do it is by showing a reduction from $A_{TM}$, which is the acceptance problem for Turing Machines (the acceptance problem for some computational model is the task of determining whether or not it accepts a given input string).

From what I understand, all that needs to be done is show that if $REGULAR_{TM}$ was decidable by some TM $R$, then another TM could use $R$ to decide $A_{TM}$, which would be a contradiction, since $A_{TM}$ is undecidable.

They construct a TM $S$ that can be used to decide $A_{TM}$. Where I'm lost is through their use of an intermediate TM, $M_2$. Here is the full description:

• $S$ = "On input $\langle M, w\rangle$, where $M$ is a TM and $w$ is a string:
1. Construct the following TM $M_2$.
• $M_2$ = "On input $x$:
1. If $x$ has the form $0^{n}1^{n}$, accept.
2. If $x$ does not have this form, run $M$ on input $w$ and accept if $M$ accepts $w$."
2. Run $R$ on input $\langle M_2 \rangle$.
3. If $R$ accepts, accept; if $R$ rejects, reject."

My two main questions are:

1. Why are we allowed to do step 2 in the construction of $M_2$? If we could just say "run $M$ on $w$ and accept if $M$ accepts", then wouldn't that be a way to show that $A_{TM}$ is decidable?
2. What exactly is the role of step 1 in the construction of $M_2$? The book says that the purpose of this TM is not to be run, but just to feed its description into $R$. The TM recognizes $\{0^n1^n\mid n \ge 0\}$ if $M$ does not accept $w$, and $\Sigma^*$ if it does, but I don't see how it does that from the description. Also, I don't see how $A_{TM}$ can be decided by using this (I'm thinking it's that the TM $M_2$ only outputs a regular language if the TM $M$ accepts $w$, but I don't understand how it can do that).

Any help is greatly appreciated, thanks!

• Please provide all the definition to make your question self contained. What is $A_{TM}$? – Ariel May 17 '16 at 18:05
• Thanks! Updated the question with this info: $A_{TM}$ is the acceptance problem for Turing machines. It determines whether or not a Turing machine accepts a given input string. While the acceptance problem for both DFAs and CFGs is decidable, it is not for TMs. – Andrew DiNunzio May 17 '16 at 18:10

## 1 Answer

This proof assumes, for the purpose of contradiction, that there exists a Turing machine $R$ deciding $R_{TM}=\left\{\langle M\rangle | \hspace{1mm} L(M) \text{ is regular}\right\}$, and uses the existence of $R$ to construct a Turing machine deciding $A_{TM}=\left\{\langle M,w\rangle | \hspace{1mm} M \text{ accepts$w$}\right\}$.

$R$ halts on every input (since it decides $R_{TM}$), so there is no problem running it (it will finally halt and either accept or reject the input). This avoids the problem of running $M$, some arbitrary Turing machine, on some input $w$, since we do not know that $M$ will finally halt.

Now, Sipser constructs a new Turing machine, $M_2$, such that:

$L(M_2) \text{ is regular} \iff M \text{ accepts$w$}$

If the above holds, then you would have $\langle M_2\rangle\in L(R) \iff M \text{ accepts$w$}$, so you could find out if $M$ accepts $w$ simply by running $R$ (which always halts) on $M_2$.

To see why this property holds, note that $M_2$ always accepts strings of the form $0^n1^n$, and it accepts any string not of this form iff $M$ accepts $w$. This means that $L(M_2)=\left\{0^n1^n | n\ge 0\right\}$ if $M$ does not accept $w$, and $\Sigma^*$ (which is regular) otherwise.

• Okay thanks, so when constructing something to be encoded and used by $R$ (like $M_2$) we are not required to make it decidable? Also, the last sentence seems a bit confusing to me. Do you mean $L(M_2)=\{0^n1^n \mid n \ge 0\}$ if $M$ does not accept $w$? From what I understand, the purpose of $M_2$ is to accept if $M$ recognizes $w$ and reject if $M$ does not accept $w$. But it also has to align with regularity, so if $M$ accepts $w$, it should decide a regular language, and if $M$ does not, it should decide a non-regular language (which arbitrarily is $0^n1^n$)? – Andrew DiNunzio May 17 '16 at 21:51
• We can give any input to $R$. Regardless of what the machine $M_2$ does, we can input it's encoding $\langle M_2 \rangle$ to $R$ and get an answer. As for your second question, you are correct, I meant $L(M_2)=\left\{0^n1^n | n\ge 0\right\}$ if $M$ does not accept $w$, now fixed. – Ariel May 17 '16 at 21:59