將ATM降低為REGULAR_TM

$$S$$為以下算法，它可以解決$$\ mathsf {A_ {TM}}$$："在輸入$$\ langle M，w \ rangle$$的情況下，其中$$M$$是一個TM和$$w$$是一個字符串：

1. 構造以下TM $$M_2$$

$$M_2$$ ="在輸入$$x$$

1. 如果$$x$$的格式為$$0 ^ n 1 ^ n$$，請接受。
2. 如果$$x$$沒有這種形式，請在輸入$$M$$=" math-container"> \$ w \$ 並接受$$M$$是否接受$$w$$
2. 運行$$R$$（機器解決$$\ mathsf {REGULAR_ {TM}} \ langle M_2 \ rangle$$中輸入。

3. 如果$$R$$接受，則接受；如果$$R$$拒絕，則拒絕。"

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$$.