從識別出圖靈機的停機問題減少


3

我正在嘗試從我的教科書中了解減少量,它不是家庭作業問題,也不是任何練習,只是試圖了解他們提出的一個例子。

這是他們給的減價:

證明我們讓R為決定REGULARTM的TM並將TM S構造為決定ATM。然後,S以以下方式工作。

S ="在輸入$ M $,$ w $時,其中M為TM,w為字符串:

  1. 構造以下TM $ M_ {2} $。

    $ M_ {2} $ ="在輸入x上:

    1. 如果x的形式為$ 0 ^ {n} 1 ^ {n} $,請接受。

    2. 如果x沒有這種形式,請在輸入w上運行M,然後如果M接受w,則接受。"

  2. 在輸入$ M_ {2} $上運行R。

  3. 如果R接受,請接受;如果R拒絕,則拒絕。"

因此,我們從決定TM語言是否正常的機器開始。我們想用它來確定TM是否在給定輸入上停止。

我的問題:如果$ w $的格式為$ 0 ^ {n} 1 ^ {n} $,該怎麼辦?好吧,$ M_ {2} $接受該字符串,僅是表單的原因。但是我們實際上從未在$ w $上運行$ M $。那麼我們如何說它會接受還是拒絕它呢?我們不知道它會做什麼,因為我們從未在$ w $上運行它。

4

Here's the key: work out what $L(M_2)$ is.

Notice that $M_2$ takes a string $x$ as input, so we are trying to identify which strings $x$ will cause $M_2$ to accept.

There are two cases:

  • Case 1: If $M$ accepts on input $w$. Then $L(M_2)=\Sigma^*$.

    In other words, in this case, it doesn't matter what $x$ is. $M_2$ will always accept on input $x$. If $x$ has the form $0^n 1^n$, then $M_2$ accepts (in step 1). If $x$ does not have the form $0^n 1^n$, then $M_2$ also accepts (in step 2). $M_2$ accepts either way; it accepts on every possible input.

  • Case 2: If $M$ does not accept on input $w$. Then $L(M_2) = \{0^n 1^n : n \in \mathbb{N}\}$.

    Let's look at why this is. If $x$ has the form $0^n 1^n$, then $M_2$ accepts in step 1. If $x$ does not have the form $0^n 1^n$, then $M_2$ runs step 2 and doesn't accept (since $M$ doesn't accept on input $w$).

So, $L(M_2)$ is one of two possibilities: it is either $\Sigma^*$ (everything) or $\{0^n 1^n : n \in \mathbb{N}\}$. Which of those two possibilities it is will depend upon $M$ and on $w$ (and in particular on whether $M$ accepts on $w$). Remember that implicitly $M_2$ is dependent upon $M$ and $w$: it's got them hard-coded into its code.

Moreover, $\Sigma^*$ is regular, but $\{0^n 1^n : n \in \mathbb{N}\}$ is not regular. So if we have a way to tell whether the language of a TM is regular or not, we have a way to tell whether $L(M_2)$ is $\Sigma^*$ or $\{0^n 1^n : n \in \mathbb{N}\}$ -- which in turn means we have a way to distinguish Case 1 from Case 2, or in other words, we have a way to tell whether $M$ accepts on input $w$ or not.

That means, if we have a way to tell whether the language of a TM is regular or not, we have a way to solve the halting problem. (It's not the same TM; it's a related TM. The way we tell whether $M$ accepts on $w$ is not by analyzing whether the language of $M$ is regular; we construct some new TM that is related to $M$ and $w$ in a crazy way, and then test whether the language of that new TM is regular or not.)


It's important to remember that $w$ is not an input to $M_2$. Instead, $w$ is just a constant that is hard-coded into the source code of $M_2$. It would be like hard-coding the value of pi as 3.1415927 in your code, except here the hardcoded constant is going to be whatever $w$ is. Each different $w$ corresponds to a different $M_2$.

P.S. I'll also repeat a crucial point from Karolis Juodelė: "Strings are not regular, languages are."