《皇帝新腦》讀書筆記
- Date: December 29th, 2015
- Author: milkpku
- Reference: The Emperor's New Mind, Roger Penrose
前言
Roger Penrose 在《皇帝新腦》中試圖回?fù)魪?qiáng)AI觀點，即人的思維過程等價于一套及其復(fù)雜的算法。他通過若干途徑進(jìn)行反駁，包括證明人腦活動的抽象模型高于算法、人腦活動的物理過程無法計算等等。在算法與人腦關(guān)系這部分，penrose主要側(cè)重于闡述算法不能超越人腦。我將其單獨抽離出來，作為一個一窺元數(shù)學(xué)深奧世界的小品。羅素悖論，哥德爾不完備定理，圖靈停機(jī)問題，看上去都相隔很遠(yuǎn)，但它們都指向了邏輯系統(tǒng)中一個相似的困難。
羅素悖論
一個集合是否能包含自身？這是集合論風(fēng)行數(shù)學(xué)界若年后羅素提出的最有挑戰(zhàn)的問題。羅素悖論點出了樸素集合論中存在的問題，即我們在以集合論為基石試圖構(gòu)建嚴(yán)密完整的數(shù)學(xué)大廈時，對基石本身的認(rèn)識就是含糊不清的。
設(shè)R={所有不包含自己的集合}，問R是否包含自身？如果R不包含自身，那么它就是一個不包含自身的集合，則根據(jù)定義R應(yīng)該包含自身；如果R包含自身，那么根據(jù)定義，R不在集合R中。
羅素采用了一個笨拙的辦法來避免羅素悖論，即對每一個集合標(biāo)定層級，每個集合只能包含層級低于自己的集合或元素。
雖然羅素悖論和之后要討論的主題略有差距，但相信了解了停機(jī)問題和不完備性定理后，我們會驚奇地發(fā)現(xiàn)，它們之間似乎有某種共通的東西，即數(shù)學(xué)對象在指向自己時會遇到的困境。
圖靈停機(jī)問題
事實上，圖靈停機(jī)問題是晚于哥德爾不完備性定理出現(xiàn)的，圖靈本人也承認(rèn)自己受哥德爾證明的啟發(fā)，寫下了停機(jī)問題。
算法與圖靈機(jī)
希爾伯特提出過其著名的希爾伯特規(guī)劃，即給定足夠的公理，運用機(jī)械推導(dǎo)，能否對所有合法表述的表達(dá)式提供正誤判斷。這也是之前一篇文章中形式主義者所懷的夢想，但后來被哥德爾無情地?fù)羲榱恕?/p>
雖然夢不再了，但有新的問題出現(xiàn)。即是否存在能在原則上一個接一個解決所有數(shù)學(xué)問題的某種一般機(jī)械步驟？問題的關(guān)鍵在于什么是“機(jī)械推導(dǎo)”，圖靈給出了他的定義，并從此打開了新世界的大門。
圖靈是這樣定義的：想象一臺在無限長磁帶上的機(jī)器，其左側(cè)有無限長的磁帶，其右側(cè)也有無限長的磁帶。磁帶由可以寫入數(shù)字的格子連接而成，可以用磁頭進(jìn)行讀寫。機(jī)器內(nèi)部還有一個記錄內(nèi)態(tài)的記錄儀器，以及一張表，用于查詢?，F(xiàn)在我們在圖靈機(jī)的右側(cè)磁帶上寫入數(shù)據(jù)（比如打孔），然后打開開關(guān)，于是它開始工作了：每一回合，它讀出磁頭所指的格子內(nèi)的數(shù)，m，并且知道自己的內(nèi)態(tài)n，那么通過查找表格，得到$(n,m) \to (n',m',d)$，即將內(nèi)態(tài)改為n'，格子內(nèi)的數(shù)改為m'，并執(zhí)行移動指令d(left, right or stay)。在機(jī)器最終停下來后，機(jī)器左側(cè)就是輸出的數(shù)據(jù)。
使用圖靈機(jī)即便是實現(xiàn)十分簡單的運算都是十分麻煩的，但至少它給出了所謂“算法”的一個嚴(yán)格的定義，即能夠由圖靈機(jī)實現(xiàn)的操作。而且，我們可以將它的那張運行表${(n,m) \to (n',m',d)| n \in all-status, m \in all-value}$通過一套編碼規(guī)則一一映射到自然數(shù)集合上，也同樣可以通過將自然數(shù)解碼來構(gòu)造圖靈機(jī)，因此圖靈機(jī)的總數(shù)和自然數(shù)的總數(shù)是一樣的！即所謂的連續(xù)統(tǒng)$\xi_0$。
通用圖靈機(jī)(Universal Turning Machine)
我們將編碼為n的圖靈機(jī)稱為$T_n$
存在一個算法，能夠模擬任何其他的圖靈機(jī)，稱為通用圖靈機(jī)，用U表示。其運行性質(zhì)為，輸入數(shù)據(jù)分兩個部分，n，k，$U(n,k) = T_n(k)$。事實上，所有現(xiàn)代的計算機(jī)都是通用圖靈機(jī)。
圖靈停機(jī)問題
是否存在一個算法，能夠在有限時間內(nèi)判定一對（算法，輸入）的組合是否停機(jī)，我們稱之為圖靈停機(jī)問題。之所以這個問題重要，是因為最終我們將證明不存在這樣一個算法，而人腦又能通過在系統(tǒng)之外的洞察判定這一對（算法，輸入）的組合是否停機(jī)。
假設(shè)存在這樣一個算法H，能夠在有限時間內(nèi)判定一對（算法，輸入）的組合是否停機(jī)，并且輸出0或1
$ H(n,k) = {0, T_n(k)不停機(jī) \ 1, T_n(k)停機(jī)$
接下來我們通過將兩個算法結(jié)合起來生成一個新的的算法：
- 先通過H(n,k)判定是否停機(jī)
- 如果停機(jī)，則輸出 T_n(k)
- 如果不停機(jī)，則輸出 0
可以表達(dá)為 $Q(n,k) = T_n(k) \times H(n, k) = U(n, k) \times H(n, k)$
接下來，定義$T_w(k) = 1 + Q(k,k) = 1 + T_k(k) \times H(k, k)$， 則當(dāng)計算
$T_w(w)$時，會遇上一個不可調(diào)和的矛盾：
$T_w(w) = 1 + T_w(w) \times H(w, w)$
- 如果$T_w(w)$會停機(jī)，那么最后得到的結(jié)果為$T_w(w) = 1 + T_w(w)$
- 如果$T_w(w)$不會停機(jī)，那么會和其定義沖突，因為等式右邊的表達(dá)式總能在有限時間內(nèi)停機(jī)。
所以不存在算法H，能夠在有限時間內(nèi)判定一對（算法，輸入）的組合是否停機(jī)。
哥德爾不完備性
哥德爾的證明思路十分簡單，其主要工作量在于將形式系統(tǒng)中的語言順利地編碼，Penrose略過了這一部分，我自然也沒有能力去細(xì)說，讓我們還是將精力集中在哥德爾思想最閃耀的那一點上。
首先，令應(yīng)用于w的第n個命題函數(shù)為$P_n(w)$。哥德爾的證明中主要的工作就是證明對于一套特定的符號系統(tǒng)，如何將其編號，在此我們直接接受其論斷，即這樣一個命題函數(shù)和變量w能夠表示任何在這一套符號系統(tǒng)下的命題。
接著，構(gòu)成這一系統(tǒng)中某一定理證明的一串命題也可以進(jìn)行編號，令$[\Pi]_n$表示第n個證明。
考慮如下的依賴于w的命題函數(shù)：$~\exist[\Pi_x 證明 P_w(w)]$，該命題論斷不存在$P_w(w)$的證明。哥德爾通過他卓越的技巧證明了這一命題函數(shù)同樣可以編碼進(jìn)前述的系統(tǒng)，我們姑且將其記為$P_k(w)$。
現(xiàn)在我們來考察一個十分怪異的命題$P_k(k)$。將其展開可以得到 $ ~\exist x[\Pi_x proof P_k(k)] = P_k(k)$。這個命題意味著：如果它為真，則不存在它的證明；如果它為假，則存在證明其為真的證明。即要么不完備，要么不一致。
哥德爾定理對于形式系統(tǒng)而言，是一個驅(qū)之不散的幽靈。假如我們將通過外部洞察得到的$P_k(k)$作為新的附加公理加入符號系統(tǒng)，記為$G_0$，則會出現(xiàn)新的不一致，我們記為$G_1$。如果接著加下去，我們得到${ G_0, G_1, G_2 ...}$ 這樣一個無限的公理系統(tǒng)，將其作為附加公理，結(jié)果怎樣？由于這個不斷附加的過程是個完全系統(tǒng)化的方案，可以將其當(dāng)做通常的公理和步驟法則的有限邏輯系統(tǒng)來重述，所以這個系統(tǒng)也有它自己的哥德爾命題，如$G_w$，那么接下來就有$G_{w+1} ...$，我們回到了起點。
個人對于penrose論證的一些觀點
（未完待補(bǔ)）
