將ATM降低為REGULAR_TM


1

考慮 $ \ mathsf {REGULAR_ {TM}} = \ {\ langle M \ rangle \ mid \ text {$ M $是一個TM而$ L(M)$是常規語言} \} $

$ 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 $ 拒絕,則拒絕。"

我試圖理解這一證明,但我確實對 $ M_2 $ 的步驟1感到困惑。

這本書說" $ M_2 $ 的工作方式是自動接受 $ \ {0 ^ n1 ^ n \n≥0 \} $ 。此外,如果 $ M $ 接受 $ w $ ,則 $ mM_2 $ 接受所有其他字符串。"

但是我不明白 $ M_2 $ 如何接受所​​有字符串。如果 $ x $ 的格式不是 $ 0 ^ n 1 ^ n $ $ M $ 不接受$$,$ L(M_2)$是否為空?還是我們可以假設有很多不同的$ x $作為$ M_2 $的輸入?

0

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 $<M,w>$ 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 $<M,w>$ 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 $<M,w>$: "build a new $TM$ where $M$ and $w$ are constants. Call it $N_{<M,w>}$, then run $R$ on input $N_{<M,w>}$ and do what $R$ does."

Inside $N_{<M,w>}$ we have our reduction. Take in mind we want this:

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

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

Now our $N_{<M,w>}$

$N_{<M,w>}$ 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_{<M,w>}$ and $S$ will accept if $R$ does:

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

Otherwise if $M$ accepts $w$, $N_{<M,w>}$ 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$.