最近更新: 2007-06-11

唉,看不懂哥德爾不完備定理的說明

最近在《不存在時間的世界》一書中,看到了哥德爾的不完備定理,其中也有提到不完備定理的的計算機形式,即圖靈的停機問題(Halting problem)。但不知是書籍翻譯還是哪裡的問題,我覺得我看不懂它的說明。

看了書中的說明後,我的程式設計經驗直接告訴我兩件事: 一、程式不具可計算性。編譯器會明確告訴我變量未定義。二、這是無窮遞迴。程式實際執行時,會發生遞迴深度超出限制或堆疊滿溢的錯誤。我總覺得書中的說明怪怪的。

在設計程式時,一個非常基本以致於我們常常忽略的事情就是:我們必須給定資料,程式才能計算。例如當我寫下:

function T() {
    if (a > b)
        return true;
    else
        return false;
}
T();

這個程式不具可計算性。多數的編譯器會直接而明確地告訴你: a, b 未定義。我不諳數學的敘述方式,照我的理解,在數學中這表示未給定 a, b 兩集合。

按照我的理解,經過一番修修改改之後,我寫下的程式形式如下列所示:

JavaScript
function T(S) {
    if ( S(S) )
        return true;
    else
        return false;
}

function test() {
    var a = 100;
    if (a > 10)
        return true;
    else
        return false;
}

print( T(test) );
print( T(T) );
C++
#include <iostream>
using namespace std;

bool T(bool (*S)(...)) {
    if ( S(S) )
        return true;
    else
        return false;
}

bool test(...) {
    int a = 100;
    if (a > 10)
        return true;
    else
        return false;
}

int main() {
    cout << T(test);
    cout << T((bool(*)(...)) T); // T(T)
}

我個人覺得怪怪的。留個紀錄,希望有人可以指點迷津。

相關文章
樂多舊網址: http://blog.roodo.com/rocksaying/archives/3451113.html

樂多舊回應
未留名 (#comment-10878907)
Mon, 11 Jun 2007 21:51:03 +0800
你如果對這個問題有興趣的話,建議您閱讀天下文化翻譯的《電腦也搞不定》。
由你上面的疑問,我覺得很可能是一些字句翻譯時所造成的誤解。
未留名 (#comment-10878989)
Mon, 11 Jun 2007 22:00:38 +0800
通常我們不會說一個「程式」具不具備可計算性;
而是說一個「問題」具不具備可計算性。

要討論一個問題具不具備可計算性有個前提,那就是這個問題必須是「明確定義的」,否則大家對問題本身沒共識,討論下去也是枉然 :p

一個問題如果具備可計算性,那就意味著可以寫一個程式來解決這個問題,且每次得到的答案都是正確的(沒有猜測的成份)

一個「不可計算」的問題,除了電腦無法解決(這裡的解決,要求每次得到的答案都要正確,不能有模稜兩可或猜測的成份)之外,人類(或數學家)也不可能解出來。
未留名 (#comment-10882797)
Tue, 12 Jun 2007 10:12:32 +0800
那麼我想轉化成電腦用語之後,「明確定義」指的就變量的定義(含輸出入資料)了吧。

在電腦程式的隱含設定下,我們通常感覺不到「不可計算」這個概念。因為編譯器會告訴我們變量未定義的錯誤。而在執行過程中,程式也會一直等待使用者輸入資料。所以我們碰到的情形,要嘛是編譯錯誤,要嘛是等待輸入。

如果問題必須可解,表示可計算性還要再加一個意義,即可在「有限次數」下得到唯一解。本文的程式是正確的,但它將無限次執行,故我們得不到解答。嗯,那麼本文的程式雖然可以編譯並執行,但只看 T(T) 這部份並不具可計算性了。

只是... 這跟不完備定理有關嗎?
未留名 (#comment-10903695)
Thu, 14 Jun 2007 03:56:06 +0800
關於哥德爾的不完備定理背後的意含,
我覺得究竟出的《數學巨人哥德爾》闡述得不錯。

哥德爾認為:
「數學世界比數學語言更複雜」(所以數學語言是不完備的)
「語言本身有時比思想更精確,但效力卻更弱,因為語言不能重現所有想像得到的模型」

(快找來看,我不要再抄書了啦 :p)

這個定理暗示的東西,和維根斯坦(Wittgenstein)在《論說(Tractatus)》提出的主張很類似,不過哥德爾用的是數學語言,維根斯坦用的是偏哲學白話文。
未留名 (#comment-10909011)
Thu, 14 Jun 2007 16:42:13 +0800
我的感想也是如此,雖然工具不同,但他們兩人都對語言與世界的關係提出了「令人失落的答案」。他們給的不是人們想要的答案。

儘管結果相似,但兩人的思想仍然沒什麼交集。哥德爾專注於實在界,認為數學可以引領他走向本質 [我以為他找尋的本質,是一種近似波普爾(Karl Popper)之客觀知識(Objective Knowledge)的世界]。而維根斯坦則把思索重點置於語言的社會性質。
未留名 (#comment-10938671)
Sun, 17 Jun 2007 12:30:14 +0800
我猜我如果一開始只接觸過 Wittgenstein 的說法,內心只會有:「喔」的反應。

但在知道 Turing 及 Godel 精確的定義及證明後,回過頭再看 Wittgenstein 的說法,才有:「哇……」的反應,深深受到該思想的衝擊。

「語言本身有時比思想更精確,但同時效力也更弱,因為語言的語法不能重現所有想像得到的模型」

「能說的明白的,比不上人類所能想像的;人們能想像出的,比不上世界各種可能存在的事物」

說穿了,不是本來就該是如此嗎?有必要大費周章特別強調嗎?

但知道這講法還經過嚴謹的數學證明,整個感覺起來就是不一樣 :)
未留名 (#comment-10940495)
Sun, 17 Jun 2007 14:55:56 +0800
哈哈,我是剛好相反。

我先看 Wittgenstein 的書,然後彷彿有一道靈光貫通我的思維。於是我真正知道什麼是「把思想說清楚」。

我接觸維根斯坦的哲學內容已經有一段時間了,再看哥德爾的內容後,反而覺得哥德爾的證明方式沒什麼思想衝擊。
未留名 (#comment-21650187)
Fri, 11 Mar 2011 13:20:20 +0800
你可以想像一下 Regular Expression
假如你能夠把一個文字規則寫成 Regexp,那麼給定任何一段有限長度的字串,你一定可以在有限時間內判別這段字串是否屬於此 Regexp,這種問題稱為判別問題。

但我們知道有很多具有明確規則的語言不可能寫成 Regexp,這是因為 Regexp 的表達能力和有限狀態機的計算力等價,這些語言超出有限狀態機的計算能力。舉例來說有個語言是

「n 個 'a' 後面接 n 個 'b',n為任意非負整數」這樣的語言雖然具有明確定義,但就是沒有辦法寫出 Regexp。

比有限狀態機更強的機器為下推機,計算能力和上下文無關文法等價,就能解決上面的問題。而最強的形式化計算機器為圖靈機,圖靈機是否和上述的 Regexp 一樣,沒辦法解決某些問題呢?

停機問題的概念是這樣,鑒於程式設計的菜鳥們偶爾會寫出陷入無窮迴圈的程式,所以有善心人士想製作一套靜態分析工具,輸入任何程式碼,這個分析程式就能在大家可接受的時間內告訴你程式是不是安全的。(注意這裡必須要用靜態分析而非委派執行或模擬,否則就失去意義了。對於會無窮迴圈的程式,委派執行就無法在有限時間內回應)

和上面 Regexp 的判別問題一樣,這也是一個對字串(即UTM程式)做出判別的問題。即使沒有看實際的證明,直覺上也會覺得這樣的靜態分析程式寫不出來,這表示存在某種有意義的字串規則超出圖靈機的計算能力。

和哥德爾不完備定理的關係,主要是UTM可以變成一個邏輯推理機,原本的證明問題就變成了判別問題。
未留名 (#comment-21661629)
Tue, 15 Mar 2011 15:26:24 +0800
所以我理解錯了。我一直以為那是證明問題,但其實是判別問題。

不過那個 regex 的例子似乎不太貼切。因為那樣的表達式寫的出來 Regexp('a?b?')。只是判定時,任何字串都符合。
問題出在 n 為任意非負整數,白話說即「兩者皆可有可無」。這「兩者皆可無」的條件,就明確立了一個不論如何都成立的旗標。

回頭看這個不完備定理,讓我聯想到《蝴蝶、斑馬與胚胎》中的一句話:
「若是人類的大腦簡單到我們可以了解,我們的認知能力就簡單到無法了解。(If the human brain was so simple that we could understand it, we would be so simple that we couldn't.)」
See http://blog.roodo.com/rocksaying/archives/14162542.html

雖然是不相同的兩個系統,但其結論,實在相似。
未留名 (#comment-21714129)
Sat, 16 Apr 2011 14:46:29 +0800
學理上探討的 Regexp 和在應用上有一點點不同,我們會希望 Regexp 能 match 所有合法的字串,並且要 reject 所有不合法的字串。以上例來說

ab (o)
aabb (o)
aaabbb (o)
abbb (x)
aab (x)
abab (x)

關鍵在於有限狀態機沒辦法進行這樣的計數
這可以靠一個名為 Pumping lemma 的數學輔理來證明