# Reduce ATM to REGULAR_TM

Consider $$\mathsf{REGULAR_{TM}} = \{\langle M \rangle \mid \text{M is a TM and L(M) is a regular language}\}$$.

Let $$S$$ be the following algorithm, which solves $$\mathsf{A_{TM}}$$: “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$$ (a machine solving $$\mathsf{REGULAR_{TM}}$$) on input $$\langle M_2 \rangle$$.

3. If $$R$$ accepts, accept; if $$R$$ rejects, reject.”

I am trying to understand this proof, but I am really confused with step 1 of $$M_2$$.

The book says "$$M_2$$ works by automatically accepting all strings in $$\{0^n1^n \mid n ≥ 0\}$$. In addition, if $$M$$ accepts $$w$$, $$M_2$$ accepts all other strings."

But I don't understand how could $$M_2$$ accept all strings. If $$x$$ is not of the form $$0^n 1^n$$ and $$M$$ does not accept , wouldn't $L( M_2 )$ be empty?. Or can we assume there are many different $x$ as an input to $M_2$?

• The Turing machine $M_2$ accepts an input $x$. The input could be any binary word whatsoever. – Yuval Filmus Dec 15 '18 at 23:47

First, note that $$M$$ and $$w$$ in $$M_2$$ are fixed. So whatever is the input, $$M$$ always accepts or rejects $$w$$. Second, note that $$M_2$$ is not built to run.

Then:

You want to map $$$$ to a regular language $$L$$ if and only if $$M$$ accepts $$w$$. Fix $$L$$, in that case you choose $$\Sigma^*$$. However, if $$M$$ rejects $$w$$ you don't want $$L$$ regular (otherwise $$R$$ will accepts), so you choose $$L'\subset L$$ such that $$L' = \{0^n1^n\}$$ which is not regular.

Now you have two cases:

1) if $$M$$ rejects $$w$$, then $$M_2$$ will accepts only the strings of the form $$0^n1^n$$, then $$R$$ will reject.

2) if $$M$$ accepts $$w$$, then $$M_2$$ will accepts all the strings of the form $$0^n1^n$$ and all other strings in $$\Sigma^*-0^n1^n$$, so $$R$$ will accept.

However in poor words, it consists to map an "yes istance" of $$$$ to a single "yes instance" of $$L$$. Let me do an example:

You want to prove that $$L=\{M |\ if\ M\ accepts\ w\ then\ M\ accepts\ flip(w) \}$$, where $$flip(w)$$ is the bitwise of all the string $$w$$ (For example if $$w$$ = $$100$$ then $$flip(w) = 011$$.), is undecidable with a reduction from $$A_{tm}$$.

Suppose $$L$$ is decidable, then exists a $$TM$$ $$R$$ that decides $$L$$. So we can build a new $$TM$$ $$S$$ that decides $$A_{tm}$$.

We will doing something like this:

$$S$$ on input $$$$: "build a new $$TM$$ where $$M$$ and $$w$$ are constants. Call it $$N_{}$$, then run $$R$$ on input $$N_{}$$ and do what $$R$$ does."

Inside $$N_{}$$ we have our reduction. Take in mind we want this:

$$M$$ accepts $$w$$ if and only if $$R$$ accepts $$L(N_{})$$

First, we fix $$L(N_{})$$ = $$\{100,011\}$$ (This is just an "yes instance" of $$L(N_{})$$

Now our $$N_{}$$

$$N_{}$$ on input $$x$$:

if $$x$$ = $$100$$ then accepts

else if $$x$$=011 then run $$M$$ on $$w$$ and do what $$M$$ does.

Then "run" $$R$$ on $$N_{}$$ and $$S$$ will accept if $$R$$ does:

if $$M$$ rejects $$w$$, the only string could be accepted by $$N_{}$$ is $$100$$ then both $$R$$ and $$S$$ will reject.

Otherwise if $$M$$ accepts $$w$$, $$N_{}$$ will accept both $$100$$ and $$011$$ then both $$R$$ and $$S$$ will accept.

So $$S$$ can decide $$A_{TM}$$ which is impossible, the "error" was to suppose the existance of $$R$$.