Formal Language - Ch12 不可決定問題與圖靈可識別語言 Undecidable Problem and Turing-recognizable language

有些問題被歸類為不可決定的問題。電腦對這類問題，只有在應該回答 Yes 時會回答 Yes，對於某些給予的內容卻無法斬釘截鐵地回答 No 。例如我們給予電腦一個程式，要求它判斷該程式是否會停止：程式若會停止，則電腦可明確地回答 Yes ，但程式若不停止，則電腦無從回答 No ，因為我們無從得知這個不停運行的程式會不會在遙遠未來的某個時刻停止。

[補充] 對角線法 (The Diagonalization Method)
對角線法是了解停機問題的前置知識，此法常在各種數學證明中使用，務必熟記！

R is uncountable
假設f(n)是對應的函數(表列出所有數字)，但對角線更改構成的新數字沒辦法對應，矛盾!
Some languages are not Turing-recognizable
一個圖靈機可以為一對應到一個字串(也就是程式碼的感覺)，因此所有圖靈機可視為所有字串的集合，因此數量與「整數」數量一樣多，為可數(countable)，因此用對角線法可證必有非non-Turing-recognizable的語言。

停機問題 (The Halting Problem)
$A_{TM}$ (Accept-Turing machine)，也就是停機問題，是一個非決定性(Undecidable)的問題，且是一個圖靈可辨識(Turing-recognizable)的問題。

$A_{TM} = \{ (M,w)\ |\ M是接受字串w的圖靈機 \}$

概念提示 : 圖靈機和描述圖靈機的符碼是兩件事，因此「圖靈機自己跑輸入的字串」和「另一個圖靈機模擬此圖靈機的符碼跑字串」是兩件事！

艾倫·圖靈在1936年用對角論證法證明了，不存在解決停機問題的通用演算法。這個證明的關鍵在於對電腦和程式的數學定義，這被稱為圖靈機。停機問題在圖靈機上是不可判定問題。這是最早提出的決定性問題之一。

停機問題包含了自我指涉，本質是一階邏輯的不自洽性和不完備性，類似的命題有理髮師悖論、全能悖論等。

停機問題是非決定性問題證明
假設停機問題有解，即：存在過程$H(P, I)$可以判斷對於程式$P$在輸入$I$的情況下是否可停機。假設$P$在輸入$I$時可停機，$H$輸出「停機」，反之輸出「無窮迴圈」，即可導出矛盾：顯然，程式本身也是一種資料，因此它可以作為輸入（例如Pascal的編譯器本身就可以用Pascal所寫成，所以程式在自己身上執行自己也是合理的），故$H$應該可以判定當將$P$作為$P$的輸入時，$P$是否會停機。然後我們定義一個過程$U(P)$，其流程如下：

$U(P)$呼叫$H(P, P)$：

如果$H(P, P)$進入死循環，$U(P)$就停機。
如果$H(P, P)$停機，$U(P)$就進入死循環。

也就是說，$U(P)$做的事情就是做出與$H(P, P)$的輸出相反的動作。

虛擬碼及其註釋表示如下：

int H(procedure,Input); // 這裡的H函式有兩種返回值，無窮迴圈(1) 或 停機(0)
int U(P)
{
    if (H(P,P) == 1){ // 如果H無窮迴圈
        return 0; // 此時會停機
    }else{ // 否則
        while(1){} // 此時會無窮迴圈
    }
}

上面把$H(P, P)$包裝在$U(P)$內，也就是用$U()$來模擬$H()$。$H()$的輸出可能出現兩種狀況：

假設$H(U, U)$輸出停機，則$U(U)$進入無窮迴圈：由定義知二者矛盾（與過程$H$的定義相矛盾，因為照$H$自己本來的定義，$H(U, U)$的結果應該和$U(U)$相同，但$U()$的定義卻是永遠輸出與$H()$相反的結果。）
假設$H(U, U)$輸出無窮迴圈，則$U(U)$停機：兩者一樣矛盾。因此，$H$不是總能給出正確答案，故前述的假設不成立，不存在解決停機問題的方法。

停機問題原文證明 (按圖放大可清楚顯示)

圖靈可識別語言 (Turing-recognizable language)

圖靈可識別語言定義
設 $M$ 是一台圖靈機，若在輸入串 $\omega$ 上 $M$ 運行後可進入接受狀態並停機，則稱 $M$ 接受串 $\omega$。$M$ 所接受的所有字符串的集合稱為 $M$ 所識別的語言，簡稱 $M$ 的語言，記作 $L(M)$。

設 $S \subseteq \Sigma^*$ 是一個語言，若存在圖靈機 $M$ 使得 $L(M) = S$，則稱圖靈機 $M$ 識別 $S$，且 $S$ 稱為圖靈可識別語言。

白話文：可識別(recognize)的意思是指吃到對的字串會報接受(Accept)，錯的「不一定」報拒絕(reject)，可能當掉。

圖靈可識別閉包性質
圖靈可識別語言在下列運算下是閉合的。就是說，如果 $L$ 和 $P$ 是兩個圖靈可識別語言，則下列語言也是圖靈可識別語言:

$L$ 的Kleene星號 $L^*$
$L$ 和 $P$ 的串接 $L \circ P$
並集 $L \cup P$
交集 $L \cap P$

注意遞歸可枚舉語言不閉合於差集和補集之下。

圖靈可識別語言(recognizable)與圖靈可判定語言(decidable)的關係
注意圖靈可識別語言和圖靈可判定語言的區別：

若 $S$ 是圖靈可識別語言，則只需存在一台圖靈機$M$，當 $M$ 的輸入 $\omega \in S$ 時，$M$ 一定會停機並進入接受狀態；當 $M$ 的輸入 $\omega \notin S$ 時，$M$ 可能停機並進入拒絕狀態，或者永不停機。
而若 $S$ 是圖靈可判定語言，則必須存在圖靈機 $M$，使得對於任意輸入串 $\omega \in \Sigma^*$，$M$ 總能停機，並根據 $\omega$ 屬於或不屬於 $S$ 分別進入接受或拒絕狀態。

並不是所有的語言都是圖靈可識別的，可以證明 (用對角線證法) 存在圖靈不可識別語言。

[補充]自我指涉問題收集
這種問題還滿有趣的^^ 下面收集一些這種好玩的自我指涉問題給大家動動腦~

全能悖論

一個全能的個體能夠創造一塊連他自己都搬不動的石頭嗎？這個問題是難以回答的。要麼能夠創造一塊他自己搬不動的石頭，要麼就不能創造一塊他自己搬不動的石頭。如果他能創造這樣的一塊石頭，那麼他就會搬不動這塊石頭，那麼他就必然不是全能的；如果他不能造這樣的一塊石頭，那他本身就已經不是全能的了。

停機問題

停機問題是判斷任意一個程序是否會在有限的時間之內結束運行的問題。如果這個問題可以在有限的時間之內解決，那麼就可以有一個程序判斷其本身是否會停機。但是，在程序停止之前，沒有辦法判斷它會不會停止。所以這是一個不可解的問題。

理髮師悖論

村子裡有個理髮師，這個理髮師有條原則是，對於村裡所有人，如果這個人不自己理髮，理髮師就給這個人理髮。如果這個人自己理髮，理髮師就不給這個人理髮。「理髮師給自己理髮嗎？」這個問題是無法回答的。

謊言悖論

公元前6世紀Epimenides謊言悖論原版的敘述很靠近生活的語言，這常被一些人認為是最早的悖論，其實不然。有個克裡特島詩人發誓說：「所有克裡特島人說的都是謊言」。

邏輯上，如果他說的這句話可信，他是克裡特島的人，根據這句話，那他說的也是謊言了，即是不可信的。這個矛盾否定了可信的解讀，只剩下不可信的可能。如果我們也能夠在邏輯上否定不可信的情況，那才構成了悖論。因為邏輯上的排中律不允許有這樣的狀況。
但是，這故事嚴格地說並不構成悖論，而是具有確定含義的。這個詩人說他家鄉人說的都是謊言，並不排斥這詩人說假話的可能。只要他家鄉還有一個老實人，這詩人就是說假話。在這個情況下這段文字沒有矛盾。唯有這樣解讀，這段的介紹文字才不自相矛盾，才有了確切的含義。
所以它唯一合乎邏輯的解讀是：敘述了一個詩人在撒謊的場景，詩人所說的話是他撒謊的證據。他說家鄉的人都是這德行，邏輯上這只能證明他本人是如此，而不及他人。

Reference

Wiki - 停機問題
http://zh.wikipedia.org/wiki/%E5%81%9C%E6%9C%BA%E9%97%AE%E9%A2%98

Wiki - 遞歸可枚舉語言
http://zh.wikipedia.org/wiki/递归可枚举语言

交大陳穎平教授正規語言講義

Pages

2015年5月25日星期一