計算複雜性（4）——我幹掉我自己：對角線方法，停機問題

學習階段：大學計算機，理論計算機。

前置知識：離散數學、通用圖靈機。

通用圖靈機

$\mathbb U(\alpha,x)$

能模擬

$\mathbb M_\alpha(x)$

的計算，而

$\alpha$

和x都是可列舉的，我們可以列出一張表：

4。1 所有TM的列舉表

在圖4。1左表中，每列從上到下列舉TM的編碼

$\alpha$

，每行從左到右列舉輸入x，使用UTM可以計算出每一格內的值。圖4。1右表是一個假想的結果，其中

$\uparrow$

表示死迴圈。

這個表中的對角線上的值為

$\mathbb M_\alpha(\alpha)$

，利用對角線做反證法，可以證明許多有趣的結論，這就是

對角線方法

（diagonal method）。請看下例：

4。1 不可計算函式UC

定義函式UC：

$\mathrm{UC}(\alpha)= \begin{cases} 0,&\mathbb M_\alpha(\alpha)=1\\ 1,&其他\\ \end{cases}\\$

這個函式是良定義的，對於每個確定的

$\alpha$

，它都有確定的結果。但是，這個函式是不可計算的！

證明：

假設存在圖靈機

$\mathbb D$

可以計算UC，則對於任意的

$\alpha$

有

$\mathbb D(\alpha)=\mathrm{UC}(\alpha)$

，取

$\alpha=\llcorner\mathbb D\lrcorner$

，那麼

$\mathbb D(\llcorner\mathbb D\lrcorner)=\mathrm{UC}(\llcorner\mathbb D\lrcorner)$

，但這就產生了矛盾：

如果

$\mathbb D(\llcorner\mathbb D\lrcorner)=\mathrm{UC}(\llcorner\mathbb D\lrcorner)=1$

，那麼

$\mathbb D(\llcorner\mathbb D\lrcorner)\ne1$

；

如果

$\mathbb D(\llcorner\mathbb D\lrcorner)=\mathrm{UC}(\llcorner\mathbb D\lrcorner)\ne1$

，那麼

$\mathbb D(\llcorner\mathbb D\lrcorner)=1$

。

也就是說

$\mathbb D(\llcorner\mathbb D\lrcorner)=1$

當且僅當

$\mathbb D(\llcorner\mathbb D\lrcorner)\ne1$

。矛盾！

故不存在這樣的圖靈機

$\mathbb D$

。

證畢。

UC函式在定義的時候，實際上是把列舉表的對角線給全部做了翻轉，如圖4。2所示：

4。2 UC對列舉表的對角線進行了翻轉

因為列舉表枚舉了所有的TM，任何一臺TM和UC在對角線上都有矛盾，故任何一臺TM都不能計算UC。

4。2 停機問題

上述UC函式不可計算似乎並不令人在意，但是有許多人們非常關心的問題都是不可計算的！

停機問題就是個著名的、具有重要意義的不可計算問題。停機函式定義如下：

$\mathrm{HALT}(\alpha,x)= \begin{cases} 1,&\mathbb M_\alpha(x)\downarrow\\ 0,&\mathbb M_\alpha(x)\uparrow\\ \end{cases}\\$

即停機問題就是判斷圖靈機

$\mathbb M_\alpha$

在輸入x上是否能停機。如果存在這樣的程式，那自然是極好的！可惜的是，停機問題是不可計算的！

這裡給出間接與直接兩種方法證明停機問題不可計算：

4。2。1 利用UC函式

假設

$\mathbb M_{\mathrm H}$

可以計算

$\mathrm{HALT}$

，則對於任意

$\alpha$

均有

$\mathbb M_{\mathrm H}(\alpha,\alpha)=\mathrm{HALT}(\alpha,\alpha)= \begin{cases} 1,&\mathbb M_\alpha(\alpha)\downarrow\\ 0,&\mathbb M_\alpha(\alpha)\uparrow\\ \end{cases}\\$

於是，我可以這樣計算函式UC：

$\mathrm{UC}(\alpha)= \begin{cases} 1,&\mathbb M_{\mathrm H}(\alpha,\alpha)=1且\mathbb U(\alpha,\alpha)=\mathbb M_\alpha(\alpha)=1\\ 0,&其他 \end{cases}\\$

也就是說，先用

$\mathbb M_{\mathrm H}$

判斷

$\mathbb M_\alpha(\alpha)$

是否停機，如果不停機就輸出0，如果停機就用通用圖靈機計算

$\mathbb U(\alpha,\alpha)$

的結果，這樣就能完美地實現函式UC的計算。然而UC是不可計算的，這個矛盾說明HALT不可計算。證畢。

4。2。2 直接用對角線方法

考慮一個叛逆的圖靈機

$\mathbb M_\beta(\alpha)$

，它首先呼叫

$\mathbb M_{\mathrm H}(\alpha,\alpha)$

判斷

$\mathbb M_\alpha(\alpha)$

會不會停機，然後：

如果

$\mathbb M_{\mathrm H}(\alpha,\alpha)=1$

，則

$\mathbb M_\beta(\alpha)$

進入死迴圈；

如果

$\mathbb M_{\mathrm H}(\alpha,\alpha)=0$

，則

$\mathbb M_\beta(\alpha)$

立刻停機。

用通用圖靈機計算

$\mathbb U(\beta,\beta)=\mathbb M_\beta(\beta)$

是否會停機呢？根據以上的設計，

$\mathbb M_\beta(\beta)$

會停機當且僅當它不會停機，矛盾。因為以上程式設計總是可行的，那麼矛盾的來源必然是

$\mathbb M_{\mathrm H}$

不可呼叫，即停機問題不可計算。證畢。

以上設計的圖靈機

$\mathbb M_\beta$

又在對角線上給自己擺了一道：如果正確的表中我應該停機，則我不停機；如果我應該不停機，則我停機。最終，

$\mathbb M_\beta$

是不滿足任意一行的圖靈機，故它不可計算，而這一切的癥結就是他呼叫了不可計算的函式HALT。

*4。3 萊斯定理

停機問題不可計算不是個例，實際上判定某TM具有任何一種非平凡性質的函式均不可計算！比如有沒有TM可以判定某TM計算函式f（x）=x？有沒有TM可以判定某TM只在輸入1001上停機？答案是都沒有！

萊斯定理

（Rice Theorem）：對於任意非平凡的可計算函式集合S（即存在可計算函式

$f_1\in S$

和

$f_2\notin S$

），則函式

$\mathrm{Rice}(\alpha)=\begin{cases} 1,&\mathbb M_\alpha\in S\\ 0,&\mathbb M_\alpha\not\in S\\ \end{cases}\\$

不可計算。

證明：

對於任一個集合S，不失一般性可令空函式（在任意輸入上均無定義的函式）

$f_\varnothing\notin S$

，而一個在輸入c上有定義的可計算函式

$f\in S$

。若

$f_\varnothing\in S$

，則交換

和

$\overline S$

進行下述討論即可。

假設存在圖靈機

$\mathbb M_{\mathrm R}(\alpha)=\mathrm{Rice}(\alpha)$

，我們可以構造一個圖靈機

$\mathbb M_{\mathrm{H}}(\alpha,x)$

計算HALT。

首先根據

$\alpha,x$

的值定義圖靈機

$\mathbb M_{\beta}(y)$

：

呼叫

$\mathbb U(\alpha,x)=\mathbb M_\alpha(x)$

，如果停機，則進行下一步；

呼叫並輸出

。

然後定義

$\mathbb M_{\mathrm{H}}(\alpha,x)$

：

根據

$\alpha,x$

的值構造

$\beta$

；

呼叫並輸出

$\mathbb M_{\mathrm R}(\beta)$

。

解釋一下上述構造的原理：如果

$\mathbb M_\alpha(x)$

停機，那麼

$\mathbb M_\beta(y)$

一定會輸出

，即

$\mathbb M_\beta(y)$

計算函式

$f\in S$

，那麼

$\mathbb M_{\mathrm{H}}(\alpha,x)=\mathbb M_{\mathrm R}(\beta)$

就會正確輸出1；如果

$\mathbb M_\alpha(x)$

不停機，那麼

$\mathbb M_\beta(y)$

對於任意輸入y也不停機，即

$\mathbb M_\beta(y)$

計算函式

$f_\varnothing\notin S$

，那麼

$\mathbb M_{\mathrm{H}}(\alpha,x)=\mathbb M_{\mathrm R}(\beta)$

也會正確輸出0。也就是說

$\mathbb M_{\mathrm{H}}(\alpha,x)$

計算的就是HALT，這產生了矛盾。

證畢。

以下連結中的知乎回答是對於萊斯定理內涵很好的解讀：

4。4 不可計算函式

在離散數學和集合論中，康托爾Cantor用對角線方法證明了實數不可列，這也是對角線方法的發源地。同樣地，我們也能用對角線方法證明

不可計算函式不可列

。

二進位制字串

$\{0,1\}^*$

是可數的，可以按字典序排列，即

$<\varnothing,0,1,00,01,10,11,000,\cdots>$

一個語言L就是從其中任選一些字串放入集合L中。所有語言的集合S就是所有判定問題的集合，假設S可列，列出下圖的左表：

4。3 對角線方法證明所有判定問題不可列

表中每一行是一個語言，1表示列首字串在該語言中，0表示列首字串不在該語言中。

但總能找到一個不在表中的語言L，即對對角線上的元素進行翻轉，這個L不在表中的任一行，因為它總在對角線上產生矛盾，這就證明了所有判定問題不可列，所有問題也自然不可列。（這也正是［0，1］間的二進位制實數不可列的證明）

由3。1。2節知所有可計算問題是可列的，而所有問題不可列，那麼不可計算問題必然不可列，可計算問題只是所有問題中的滄海一粟！

這一篇所討論的可計算性理論不是計算複雜性的重點，但對角線方法在計算複雜性的證明中運用廣泛。下一篇將會回到對於時間與效率的討論。

小蜜蜂問答

小蜜蜂問答

計算複雜性（4）——我幹掉我自己：對角線方法，停機問題

推薦文章

小蜜蜂問答

小蜜蜂問答

計算複雜性（4）——我幹掉我自己：對角線方法，停機問題

相關文章

脫式計算方法怎麼做？

什麼叫做可去間斷點？

飛機票如果買了後不坐可以退票嗎？

如何摺紙青蛙？

推薦文章