卷首語

幾天前把剛買的《證明達(dá)爾文》看完了。
　　沒有即可就寫書評，主要是因?yàn)槭诸^上的事太多了，各種各樣的事情。
　　今天在外面忙完，終于可以寫點(diǎn)東西了。

本文是關(guān)于《證明達(dá)爾文》的。內(nèi)容雖然圍繞這本書，但基本都不在這本書里，所以，其實(shí)你可以認(rèn)為這篇東西和這本書一點(diǎn)關(guān)系沒有……

關(guān)于《證明達(dá)爾文》

先來說下這本書吧。

實(shí)話實(shí)說，這本書不咋地。
　　這本書最大的毛病，就是前面一半給人的感覺是帶球在對方門前盤帶，盤帶了45分鐘，球就是不被你搶走，但我就是不射，就不射呀就不射，氣死你！
　　尼瑪，這段話說得讓我想到了某些很不好的東西。。。
　　可以說，第四章后半部分之前的所有內(nèi)容都可以幾句話交代清楚，但作者——著名數(shù)學(xué)家，可計(jì)算理論開創(chuàng)者，蔡汀常數(shù)的發(fā)現(xiàn)者，格雷戈里·蔡汀——愣是用了三章半的篇幅來反反復(fù)復(fù)。
　　好吧，可能是因?yàn)槲覀€(gè)人因?yàn)楸容^忙所以希望可以快速看完這本書的緣故所以這部分沒有耐下心，如果你打算看這本書的話，可以不用理會(huì)我上面這段的吐槽。

就核心思想來說，這本書的內(nèi)容可以歸納為以下這幾點(diǎn)：

1. 馮·諾依曼提出DNA就是代碼；
2. 蔡汀提出了基于代碼的DNA演化模型，并利用蔡汀停機(jī)概率與忙海貍問題證明了累積演化過程遠(yuǎn)優(yōu)于隨機(jī)選擇，且足夠接近神創(chuàng)論。

第一點(diǎn)到第二點(diǎn)似乎很跳躍哦。

本文從下面開始的內(nèi)容，就是圍繞上述兩點(diǎn)展開的——然后基本就開始脫離那本書了。

構(gòu)型空間中的演算

有一個(gè)問題是曾經(jīng)困擾我很久的，那就是，如何證明遺傳算法為代表的高級算法的確“足夠優(yōu)秀”？
　　和這個(gè)問題相關(guān)的另一個(gè)問題是這樣的：高級算法在多大程度上能找到全局最優(yōu)解而非局部最優(yōu)解？
　　雖然我并沒有學(xué)過計(jì)算理論，對遺傳算法等高級算法的認(rèn)識也有限，但憑借著多年常開不閉的腦洞，我還是鼓搗出了一個(gè)解決這些問題的思路。

讓我們來構(gòu)思一個(gè)態(tài)空間C，或者說是構(gòu)型空間Configuration Space（物理上也稱為?？臻g，反正就是個(gè)名字），它是離散的。
　　這個(gè)空間是D維的，每個(gè)維度都可以分為N個(gè)格子，于是這總共N^D個(gè)格子就是整個(gè)空間的所有可能狀態(tài)。
　　每個(gè)狀態(tài)或者說是格子就代表了一種參數(shù)配置，在遺傳算法中可以近似地看作是基因配型。
　　因此，我們可以說，這個(gè)空間的每一個(gè)格點(diǎn)，就對應(yīng)了算法所要解決問題的一個(gè)“解”，只不過顯然其中絕大部分的解都不是最優(yōu)解，無論是全局最優(yōu)還是局部最優(yōu)。
　　接著，所有遺傳算法或者退火算法或者蟻群算法，等等等等，所做的事可以分解為以下幾步：

1. 為該構(gòu)型空間建立可控勢函數(shù)V(q∈C, t)，其中q是空間中格點(diǎn)，t是全局時(shí)間，可通過調(diào)節(jié)t來調(diào)節(jié)整個(gè)勢，并要求問題的局部最優(yōu)解或者全局最優(yōu)解是勢V的極小值點(diǎn)；
2. 對空間中給定點(diǎn)集{q_i}，構(gòu)造依賴勢V的步進(jìn)函數(shù)S，使q_(i+1) = S({q_i})滿足某個(gè)泛函不等式：F[q_(i+1),{q_i},V]≤0。

根據(jù)上面兩個(gè)基本構(gòu)造，我們可以證明，上述點(diǎn)集序列{q_i}最后肯定會(huì)停在某個(gè)確定的q上，使得泛函不等式取到=0這個(gè)停止條件（但=0并不必然代表點(diǎn)集序列停止在某個(gè)確定的q上）。

用直觀的方式來說，這就等于在D維空間上增加了一維，形成一個(gè)D+1維空間，而V構(gòu)成了這個(gè)空間上的一個(gè)曲面，這個(gè)曲面對應(yīng)了原本所求問題對各可能解的匹配程度，從而真正好的解都是這張曲面上的“谷”——其中，絕大部分的谷是局部最優(yōu)解，而那個(gè)最低的谷是全局最優(yōu)解。
　　接著，第二條就是構(gòu)造在這張曲面上從給定點(diǎn)出發(fā)，下一步怎么走，才能更接近我們所要的谷。

這么說太抽象了，我們以經(jīng)典的最短路徑問題來看一下一些常見的高級算法是如何實(shí)現(xiàn)上述兩步的吧。

最短路徑問題

所謂最短路徑問題，是指，如果存在N個(gè)點(diǎn)，有M條線段連接著N個(gè)點(diǎn)，求從指定的點(diǎn)A到指定的點(diǎn)B的最短路徑。

這是學(xué)習(xí)高級算法的入門問題。

在利用電腦構(gòu)造的高級算法解決這個(gè)問題之前，我們先來看一下物理上是如何解決這個(gè)問題的：

建造一個(gè)固定比例的模型，用N個(gè)圓環(huán)代表那N個(gè)點(diǎn)，然后用一跟線連接點(diǎn)i和點(diǎn)j對應(yīng)的圓環(huán)i和圓環(huán)j，線的長度等比于問題中點(diǎn)i和點(diǎn)j的距離。模型全部制作完成后，你一手拿點(diǎn)A對應(yīng)的圓環(huán)A，一手拿點(diǎn)B對應(yīng)的圓環(huán)B，然后兩手張開，當(dāng)A和B之間的線都繃直不能再拉的時(shí)候，你就得到了從A到B的最短路徑。

搞算法的人是不是被嚇尿了？
　　曾經(jīng)某次學(xué)習(xí)算法的時(shí)候看到這個(gè)著名的問題，我第一個(gè)反應(yīng)就是動(dòng)手做這么一套模型，然后一起學(xué)算法的同學(xué)直接說我離經(jīng)叛道這輩子都當(dāng)不了軟件工程師。

為什么我們的高級算法不能像上面的動(dòng)手做模型一樣簡單明了？
　　為了分析這個(gè)問題，我們先要理清上述動(dòng)手做模型中，當(dāng)你最后將A和B左后拉開的時(shí)候到底發(fā)生了什么——
　　這里實(shí)際發(fā)生的，是每個(gè)圓環(huán)，每條線段，實(shí)際上都在你拉開的過程中進(jìn)行著自適應(yīng)的調(diào)整與改變——也就是說，我們這里有總共N+M個(gè)作出應(yīng)急反應(yīng)的計(jì)算單元，所以在你拉開的時(shí)候，整個(gè)模型其實(shí)正在進(jìn)行一場高效的并行計(jì)算。
　　而作為比較，我們的計(jì)算機(jī)，無論算法多牛逼，計(jì)算機(jī)的芯片有多少核，是否采用超線程技術(shù)，本質(zhì)上還是串行計(jì)算，而非并行的。

現(xiàn)在回到算法上來。
　　如果我們用遺傳算法或者退火算法來解決這個(gè)問題，是一個(gè)怎么樣的過程？

首先，退火和遺傳，或者別的什么算法，解的形式肯定是開頭為A結(jié)尾是B的一個(gè)字符串或者說是點(diǎn)集，而算法所需的適應(yīng)函數(shù)的最合適選擇，就是這個(gè)點(diǎn)集對應(yīng)的折線的長度。
　　用我的模型來說，此時(shí)構(gòu)型空間總共有N-2維，每個(gè)維度都有N-2個(gè)獨(dú)立格點(diǎn)，整個(gè)構(gòu)型空間的勢能函數(shù)V就是一個(gè)給定點(diǎn)q=(q_1,q_2...q_{N-2})就是這個(gè)序列對應(yīng)的折線的長度——很顯然，此時(shí)勢V的最低點(diǎn)就是我們這個(gè)問題的解——這個(gè)格點(diǎn)對應(yīng)的序列給出的就是連接A和B的最短路徑。
　　PS：這里需要注意，優(yōu)于連接N個(gè)點(diǎn)的路徑只有M條，而M可能不是N(N-1)/2，所以可能有些點(diǎn)之間沒有路徑連接，此時(shí)如果在構(gòu)型空間中出現(xiàn)一個(gè)格點(diǎn)代表的點(diǎn)集序列要求這樣的點(diǎn)相連，那么就給出一個(gè)無窮大勢，表示斷開。
　　因此，現(xiàn)在的一條基因的長度是N，其中開頭是A，結(jié)尾是B。如果一條實(shí)際路徑不需要通過所有N個(gè)節(jié)點(diǎn)，那么可以認(rèn)為在某一位開始都是B，或者在某一位之前都是A。

接著，退火算法給出了一個(gè)從一個(gè)點(diǎn)擴(kuò)散出一群點(diǎn)的（燃燒）策略：
　　對一個(gè)點(diǎn)集序列做隨機(jī)的改變——這里的改變就是改變（除了起點(diǎn)和終點(diǎn)）某一點(diǎn)的值——并將改變后的點(diǎn)記錄下來，每一輪產(chǎn)生V個(gè)點(diǎn)，接著將這V個(gè)新點(diǎn)和老點(diǎn)一起排序，根據(jù)時(shí)間來決定保留多少，留下的點(diǎn)進(jìn)行下一輪擴(kuò)散。
　　遺傳算法在這方面其實(shí)本質(zhì)上是相同的，但對于什么是改變則略有不同。
　　遺傳算法中的基因改變分為變異和交換兩部分。而在通常情況下，變異又分為點(diǎn)突變和段交換及段反序，這都發(fā)生在一條基因上，不與別的基因交互。而交換過程則是兩條基因之間交換彼此的（對位或非對位）基因段。
　　在最短路徑問題中，遺傳算法的變異中的點(diǎn)突變等于退火算法的燃燒。段交換和段反序顧名思義，不需要太多解是?；蚪粨Q則是遺傳算法所特有的，兩條基因G1和G2交換一段等長的點(diǎn)序列。

現(xiàn)在，從我的構(gòu)型空間的角度來復(fù)述一下上述過程。
　　退火算法可以看作是在已知點(diǎn)的鄰域內(nèi)隨機(jī)選擇V個(gè)點(diǎn)，然后選擇包括舊點(diǎn)在內(nèi)的V+1個(gè)點(diǎn)中勢最小的前P(t)個(gè)保留，進(jìn)入下一代繼續(xù)燃燒。從而是一個(gè)在鄰域內(nèi)通過隨機(jī)行走找到勢更小位置的算法，類似蒙特卡羅（好吧，也不是那么類似）。
　　而遺傳算法的行為則有四類：

1. 鄰域內(nèi)的隨機(jī)行走（對應(yīng)點(diǎn)變異）；
2. 旋轉(zhuǎn)（對應(yīng)段交換）；
3. 反射（對應(yīng)段反序）；
4. 兩個(gè)點(diǎn)之間取一個(gè)中點(diǎn)（對應(yīng)基因交換，當(dāng)然，并不真的是中點(diǎn)，而是“中間區(qū)域內(nèi)的某個(gè)點(diǎn)”）。

可以看到，遺傳算法中點(diǎn)擴(kuò)散的手段明顯多了很多。
　　好了，現(xiàn)在如果來演化這兩個(gè)算法，我們實(shí)際上看到的就是這樣的——
　　退火算法看上去就是在一座山上，一群人靠著隨機(jī)行走，不斷地往谷底走去，最后走到了谷底。
　　而遺傳算法，是一群人，不斷通過隨機(jī)行走、乾坤大挪移（旋轉(zhuǎn)與反射）以及和朝著別的人的瞬間移動(dòng)（基因交換）來走向谷底。。。
　　這么說很抽象，而且，就一般的最短路徑來說，第一種隨機(jī)行走就足夠走到谷底了。但是，如果現(xiàn)在整個(gè)構(gòu)型空間中除開存在一個(gè)全局最低點(diǎn)，還存在很多局部最低點(diǎn)的話，隨機(jī)行走就不是好主意了——隨機(jī)行走很容易走近了某個(gè)局部最低點(diǎn)，然后就走不出來了，因?yàn)樗男袨檫壿嬀褪请S機(jī)行走，然后保留走向勢能低的那些點(diǎn)，從而如果一個(gè)局部最低點(diǎn)距離全局最低點(diǎn)以及該點(diǎn)所影響的開始下落的坡區(qū)足夠遠(yuǎn)，那么通過局部的隨機(jī)行走是很難走出的。
　　當(dāng)然，退火算法中點(diǎn)變異的范圍可以不是“鄰域”，這在一定程度上緩解了這個(gè)問題，但這導(dǎo)致的副作用是當(dāng)足夠靠近最低點(diǎn)的時(shí)候，往往會(huì)由于步子邁得太大而錯(cuò)過——所以退火才有一個(gè)降溫函數(shù)，來逐漸縮小變異或者說燃燒范圍，最后凝結(jié)到最優(yōu)點(diǎn)。這種前期高溫后期降溫的方法，就是希望前期廣撒網(wǎng)，將點(diǎn)散布到所有局部最優(yōu)點(diǎn)的坡區(qū)，然后通過降溫來凍結(jié)在每個(gè)局部最優(yōu)點(diǎn)上，從而通過比較來找出全局最優(yōu)點(diǎn)。不得不說這個(gè)想法很好，但降溫函數(shù)或者說熄火函數(shù)需要選擇得好，不然還沒找到所有局部最優(yōu)點(diǎn)的坡區(qū)就降溫的話，那就可能漏掉解。
　　而遺傳算法由于不單單是隨機(jī)行走，還存在別的方法來“繞出”局部谷底，所以相對退火算法來說就有了更多的離開局部最優(yōu)解陷阱的途徑——也所以遺傳算法不需要退火。
　　可以看到，退火算法的高溫期的作用就是為了避免局部谷陷阱，低溫期的作用是凝結(jié)到谷底。而遺傳算法點(diǎn)變異的作用是為了凝結(jié)到谷底，段交換、段反序和基因交換的作用是為了避免局部谷陷阱——特別是基因交換，只要初始基因足夠多樣性，那么最后就可能行為包圍全局最優(yōu)點(diǎn)的局面，然后通過基因交換來尋找中間區(qū)域，便有可能找到全局最優(yōu)點(diǎn)。

算法比較

通過分析，我們知道，對于這類算法所處理的問題，往往具有如下難點(diǎn)：

1. 構(gòu)型空間龐大，且不存在解析手段；
2. 存在多個(gè)局部最優(yōu)解，從而存在局部谷陷阱；
3. 有可能難以精確找到谷底。

所有遺傳算法這樣的高級算法都是通過各種方式來繞開上述三個(gè)問題——事實(shí)上，這些算法的誕生本身就是因?yàn)榈谝粋€(gè)問題，否則就可以使用暴力窮舉了。
　　面對第二和第三個(gè)問題，歸根到底，其實(shí)可以總結(jié)為兩點(diǎn)：
　　如何更好地評價(jià)一個(gè)解“有多接近最優(yōu)解”，另一個(gè)就是“如何從一個(gè)解生成另一個(gè)解”。
　　而，第一個(gè)問題就是構(gòu)型空間中的勢能V的選擇問題，第二個(gè)問題則是點(diǎn)生成函數(shù)S的選擇問題。因此，所有問題歸根到底都是V和S的選擇問題。

OK，關(guān)于如何選擇V和S更好，這個(gè)問題這里不談，讓我們回到本文最開始的目的——如何評價(jià)一般而言的V和S下，遺傳算法等算法在結(jié)局問題方面的優(yōu)秀程度？

好了，現(xiàn)在讓我們先看兩個(gè)極端。

在最短路徑問題中，最快的方法，就是我所提到的“物理方法”，或者說是“動(dòng)手做模型法”。
　　這里，你只需要一次操作：拉開A和B（前期準(zhǔn)備不算）。
　　由于物理模型的并行性，直接上的運(yùn)算量是N+M，或者說就是O(N)的計(jì)算量。
　　而，如果使用暴力窮舉破解，由于構(gòu)型空間總共有(N-2)^(N-2)個(gè)狀態(tài)，所以計(jì)算量就是O(N^N)。
　　那么，遺傳算法和退火算法等的計(jì)算量是多少呢？
　　如果只考慮隨機(jī)行走，那么從一個(gè)點(diǎn)出發(fā)，隨機(jī)行走到谷底，所需要的計(jì)算量差不多為O(N log(N))。

哈，可以看到，雖然高級算法找到最優(yōu)解（不考慮是否是全局最優(yōu)解）所用的計(jì)算量比物理手段多，但明顯遠(yuǎn)優(yōu)于暴力窮舉（廢話，不然還要這些“高級”算法干嘛？）。
　　而且，更有意思的是，比較這兩個(gè)手法的計(jì)算量，我們發(fā)現(xiàn)，這些高級算法的計(jì)算量“足夠接近”物理手段。
　　而這個(gè)，就是蔡汀所力圖證明的東西。

再談基因

在繼續(xù)下一個(gè)篇章的東西前，讓我們回頭來看看遺傳算法與退火算法。

重溫一下我們所面臨的三個(gè)問題：

1. 構(gòu)型空間龐大，且不存在解析手段；
2. 存在多個(gè)局部最優(yōu)解，從而存在局部谷陷阱；
3. 有可能難以精確找到谷底。

第一個(gè)問題是高級算法的使命，我們不談。
　　為了解決第二與第三個(gè)問題，退火算法采用的是高溫燃燒與退火凝結(jié)，分別應(yīng)對這兩個(gè)問題。而遺傳算法的手段是利用點(diǎn)變異來解決第三個(gè)問題，而通過基因段的反序、基因內(nèi)交換以及基因間交換這些手段來解決第二個(gè)問題。
　　但，除了上述這些內(nèi)容，有一個(gè)很有趣的特色我們都沒有提及，那就是——每次都保留一組基因，而不是只選擇唯一的最優(yōu)基——無論是遺傳算法的基因池還是退火算法的燃點(diǎn)集。
　　這個(gè)基本特點(diǎn)為什么一定要存在——當(dāng)然了，對于遺傳算法，必須要有超過一個(gè)基因才能實(shí)施基因間片段交換，這個(gè)理由我們不考慮。
　　讓我們構(gòu)思一個(gè)充滿局部谷陷阱的問題的構(gòu)型空間，如果我們每次只保留一個(gè)最優(yōu)點(diǎn)，那么如果我們一開始不在局部最優(yōu)解所在的坡區(qū)，那么下一步通過隨機(jī)行走可以走到最優(yōu)解所在坡區(qū)的概率，等于最優(yōu)解坡區(qū)中比當(dāng)前所在位置低的區(qū)域的“面積”S(q)與隨機(jī)步行范圍Q(t)的交集S(q)∩Q(t)與Q(t)的比。而如果已經(jīng)在最優(yōu)解的坡區(qū)，那么下一次通過隨機(jī)行走離開的概率就是局部非全局最優(yōu)解坡區(qū)地獄當(dāng)前點(diǎn)位置的“面積”O(jiān)(q)∩Q(t)與Q(t)的比。
　　可見，如果問題足夠特殊或者V選擇不佳，導(dǎo)致S(q)很小的話，那么只保留一次最優(yōu)點(diǎn)就很可能導(dǎo)致錯(cuò)過全局最優(yōu)解。
　　因此，之所以不只保留一個(gè)最優(yōu)點(diǎn)，而是保留一批較優(yōu)點(diǎn)，其根本原因就是為了避免一個(gè)點(diǎn)落入坑里爬不出來的情況發(fā)生。
　　也就是說，所有那些非最優(yōu)的備胎點(diǎn)的存在，就是為了避免最優(yōu)的高富帥出家當(dāng)和尚——所以，女生們，知道了不？多備點(diǎn)備胎總是沒錯(cuò)的！【哎？似乎什么不對的東西混進(jìn)來了……】

如果將最優(yōu)點(diǎn)視為“正確”的，那么這種保留一堆非最優(yōu)的“錯(cuò)誤”點(diǎn)的容錯(cuò)手段，也可以看作是將未來的希望寄托在不夠完美的“錯(cuò)誤”之中——因此，從這點(diǎn)我們回過頭來看上個(gè)世紀(jì)的經(jīng)典科幻阿西莫夫的《永恒的終結(jié)》，我們可以發(fā)現(xiàn)，修正錯(cuò)誤從某種程度上來說也可以看作是扼殺未來。

這點(diǎn)非但在遺傳算法之類的高級算法中很重要，在描述和解決和演化相關(guān)的問題時(shí)，也很重要。

信息空間中的演化

上面所描述的構(gòu)型空間作為解決問題，特別是數(shù)學(xué)問題或者工程問題，是很好的。
　　但，構(gòu)型空間本身也有很大的局限性。
　　比如，構(gòu)型空間中的每個(gè)構(gòu)型都是表現(xiàn)性，因而，所有無表現(xiàn)的基因就無法在構(gòu)型空間中被體現(xiàn)出來——這也就是說，構(gòu)型空間無法合理體現(xiàn)基因中“備而不用”的那些預(yù)備信息。
　　其次，構(gòu)型空間是固定的，不具備“創(chuàng)造性”——而這就是蔡汀利用圖靈機(jī)在證明進(jìn)化論的過程中所構(gòu)造出來的東西。

上述這兩個(gè)問題，歸根到底都表示一個(gè)意思：構(gòu)型所能蘊(yùn)含的信息量太低。
　　為此，我們就必須使用比構(gòu)型空間更優(yōu)的對象，那就是：信息空間。

按照蔡汀的思路，我們更應(yīng)該使用“圖靈機(jī)空間”或者“代碼空間”，但我個(gè)人認(rèn)為使用信息空間這個(gè)名詞就足夠了。

信息

先來說一下什么是信息。

對于信息的定義，其實(shí)還是存在著一些模糊性的。
　　比如，物理上的信息最初被看作“熵”的對立面，也就是無序的對立面：有序。

數(shù)學(xué)家兼信息論創(chuàng)始人香農(nóng)在題為“通訊的數(shù)學(xué)理論”的論文中指出：“信息是用來消除隨機(jī)不定性的東西”。
　　控制論創(chuàng)始人維納認(rèn)為“信息是人們在適應(yīng)外部世界，并使這種適應(yīng)反作用于外部世界的過程中，同外部世界進(jìn)行互相交換的內(nèi)容和名稱”，它也被作為經(jīng)典性定義加以引用。
　　向量分析方法創(chuàng)始人美國著名物理化學(xué)家吉布斯則認(rèn)為“熵”是一個(gè)關(guān)于物理系統(tǒng)信息不足的量度。

有序即信息，負(fù)熵即信息，這是信息論創(chuàng)立初期在物理上的反映。
　　對于最新的現(xiàn)代信息論中的信息為何，這個(gè)定義就太豐繁復(fù)雜了，流派繁多。
　　當(dāng)然，雖然我們說不清信息的具體定義，但這倒并不妨礙數(shù)學(xué)家物理學(xué)家信息論學(xué)家堅(jiān)信信息是世界的基礎(chǔ)——著名物理學(xué)家約翰·惠勒（也就是費(fèi)曼的老師，多宇宙理論創(chuàng)始人Everett的老師，《星際穿越》科學(xué)顧問、《黑洞與時(shí)間彎曲》的作者、廣義相對論圣經(jīng)MTW的作者基普·索恩的老師，當(dāng)然，他本身也是MTW的作者之一）在晚年提出的“It From Bit”也可以被認(rèn)為是現(xiàn)代信息物理流的前身（當(dāng)然了，IFB所提出的位宇宙還不完全等同于信息宇宙），進(jìn)而現(xiàn)代很多人甚至認(rèn)為信息是萬事萬物的基礎(chǔ)，物理的本質(zhì)就是研究信息。

就個(gè)人來看，信息的意義有兩層：一層，信息反應(yīng)了對象的結(jié)構(gòu)以及對象間的聯(lián)系；另一層，信息體現(xiàn)了創(chuàng)造的可能性。

而，無論是描述性的信息，還是創(chuàng)造性的信息，最能合理體現(xiàn)信息的，便是圖靈機(jī)。

圖靈機(jī)的世界

我們構(gòu)造一個(gè)信息空間，其中每個(gè)格點(diǎn)都代表一個(gè)圖靈機(jī)。
　　但并非任意的圖靈機(jī)，而是一種特殊的通用圖靈機(jī)，其中包含了各種可以生成的別的圖靈機(jī)——無論能否停機(jī)。
　　事實(shí)上，這種圖靈機(jī)可以根據(jù)基因來實(shí)現(xiàn)各種任務(wù)，包括生成多臺(tái)別的圖靈機(jī)（Y算子，當(dāng)然了）。
　　這么一來，我們也可以說信息空間的每個(gè)格點(diǎn)都是一段基因，然后這臺(tái)通用圖靈機(jī)根據(jù)基因完成各種任務(wù)，包括生成可以完成特定任務(wù)的圖靈機(jī)——哪怕是預(yù)期要完成某個(gè)人物但當(dāng)前還沒完成故而不會(huì)停機(jī)或者以錯(cuò)誤停機(jī)的圖靈機(jī)。
　　這就是信息空間中基因的創(chuàng)造性的體現(xiàn)。
　　現(xiàn)在，信息空間的基因已經(jīng)可以很好地解決之前提出的第一個(gè)任務(wù)了——蘊(yùn)含非表現(xiàn)型的基因片段，從而使得備而不用備戰(zhàn)未來的基因成為可能。
　　另一方面，由于圖靈機(jī)本身的強(qiáng)大，現(xiàn)在的信息空間可以說容納了一切可計(jì)算的問題，這個(gè)空間已經(jīng)足夠龐大與強(qiáng)大，當(dāng)然，如果要考慮的是生物的演化的話，這個(gè)可計(jì)算看空間顯然還不夠強(qiáng)大與龐大——當(dāng)然，站在It From Bit的位宇宙的角度，也許已經(jīng)足夠了。
　　從而，第二個(gè)問題雖然不能算是很完美地解決，但至少現(xiàn)在的信息空間已經(jīng)蘊(yùn)含了“創(chuàng)造性”。

演化

描述完了作為背景的空間，現(xiàn)在來回過頭來看看我們的問題。

在態(tài)空間中，遺傳算法等算法要研究的問題往往都具有若干個(gè)全局最優(yōu)解，以及更多的局部最優(yōu)解。但這個(gè)提法在描述實(shí)際的生物演化時(shí)卻變得不可行——生物的演化并不存在最優(yōu)解。
　　所以，如果我們要考慮的是信息空間中的演化的話，我們就不能繼續(xù)認(rèn)為還存在全局最優(yōu)解，從而演化的目的不似之前是找到全局最優(yōu)解，而是能找到局部最優(yōu)解就足夠了。
　　而，現(xiàn)在信息空間中的勢V，也不再簡單的是關(guān)于空間中位置的函數(shù)了。
　　現(xiàn)在信息空間中存在一系列特定的任務(wù){(diào)T}，每個(gè)任務(wù)都需要圖靈機(jī)來完成。因此，現(xiàn)在信息空間中的每個(gè)點(diǎn)所對應(yīng)的基因都將生成圖靈機(jī)來完成各任務(wù)，并根據(jù)完成的情況來確定勢能V——這就是現(xiàn)在的勢能的定義。
　　而，各種不同的演化方案，就和此前的遺傳算法或者退火算法一樣，所要做的就是不斷利用已有的點(diǎn)來生成或者說到達(dá)新的點(diǎn)，從而盡力到達(dá)一個(gè)“安全”的區(qū)域，不被淘汰（是否被淘汰以每個(gè)點(diǎn)的勢V及其構(gòu)成的集合{V}決定）。
　　因此，其實(shí)問題本身沒有變——在一個(gè)空間中，存在勢V與演化函數(shù)S，然后來查看S是否可以確?！把莼背掷m(xù)進(jìn)行，并能以多快的速度實(shí)現(xiàn)某個(gè)預(yù)定的目標(biāo)——比如“演化出眼睛”或者“征服宇宙”。
　　而真正發(fā)生改變的，只不過是我們現(xiàn)在是在信息空間中完成這項(xiàng)任務(wù)，而每個(gè)點(diǎn)都依靠生成的圖靈機(jī)來解決問題。
　　因此，本質(zhì)上來說，生命的演化（在這個(gè)理論中）就可以被描繪成信息空間中的通過已知的點(diǎn)來獲得下一點(diǎn)點(diǎn)群的過程——事實(shí)上，蔡汀第四章的標(biāo)題就是：軟件空間中的隨機(jī)行走。

讓我們回到《證明達(dá)爾文》這本書。
　　這本書中的內(nèi)容，其實(shí)就是上面所提出的這個(gè)范疇中的一個(gè)問題——現(xiàn)在在信息空間中我們要解決的問題是“獲得更精一位的忙海貍問題的解”。
　　因此，可以說，蔡汀所證明的就是在上述大背景下的一個(gè)特例中，累進(jìn)式演化足夠接近神創(chuàng)——而這點(diǎn)其實(shí)就類似在最短路徑問題中我們所證明了的遺傳算法與退火算法的“演化”速度足夠接近物理模型方法。

雖然對上述模型我們不能給出足夠精確的證明——事實(shí)上我們所能做的也不過是和蔡汀所作的一樣，針對某個(gè)特定的問題來給出準(zhǔn)確且精確的證明——但并不妨礙我們?nèi)ハ嘈牛谛畔⒖臻g中的這個(gè)演化問題，應(yīng)該可以獲得和構(gòu)型空間中的演算問題一樣的結(jié)論：
　　神創(chuàng)和物理模型法一樣，所需的演化步驟為O(N)；
　　暴力窮舉法需要的演化步驟為O(整個(gè)空間的大小)；
　　累進(jìn)式演化所需要的演化步驟為O(N log(N))（當(dāng)然，這個(gè)結(jié)論和蔡汀所給出的N log(N)²已經(jīng)明顯不同了）。
　　從而，我們差不多可以認(rèn)為，累進(jìn)式演化在單位時(shí)間里具有差不多可以匹敵神創(chuàng)的威力（好吧，其實(shí)差距還是很大的。。。因?yàn)镹本身超級大。。。），至少也比暴力窮舉高效了很多很多（這句是廢話）。

小結(jié)

上面的討論基本完全是脫離了蔡汀的那本《證明達(dá)爾文》而作的，所以，其實(shí)和我看不看這本書沒啥關(guān)系。。?？催@本書只不過是給了我寫這篇文章一個(gè)借口而已。

這里有幾個(gè)概念是最核心的：

<big>1. 數(shù)學(xué)本身蘊(yùn)含了無窮的創(chuàng)造性</big>
　　這點(diǎn)是蔡汀在前三章里不斷強(qiáng)調(diào)的，也是一個(gè)和我們?nèi)粘Ｉ畹慕?jīng)驗(yàn)相近又相遠(yuǎn)的一個(gè)概念。
　　從那個(gè)著名的數(shù)學(xué)不可思議的有效性的哲學(xué)論題中，我們已經(jīng)可以感受到數(shù)學(xué)本身所蘊(yùn)含的無窮創(chuàng)造性，但同時(shí)另一方面，數(shù)學(xué)作為一門學(xué)科給人的感覺是在不斷構(gòu)造數(shù)學(xué)概念解決數(shù)學(xué)問題，但似乎并不具備創(chuàng)造力——具有創(chuàng)造力的是數(shù)學(xué)家，而不是數(shù)學(xué)。
　　這種觀念（也許存在，也許不，反正我個(gè)人認(rèn)為數(shù)學(xué)本就具備無窮的創(chuàng)造性潛力）在圖靈與馮·諾依曼等人所建立的杰出的開創(chuàng)性工作后其實(shí)就已經(jīng)被終結(jié)了。
　　事實(shí)上，圖靈機(jī)本質(zhì)上可以歸結(jié)為數(shù)學(xué)上的函數(shù)——對，圖靈機(jī)最早被提出時(shí)就是一個(gè)七元函數(shù)——從而圖靈機(jī)的創(chuàng)造性與創(chuàng)造力本質(zhì)上也只不過是數(shù)學(xué)的創(chuàng)造性與創(chuàng)造力的一部分而已。

<big>2. 基因蘊(yùn)含了創(chuàng)造的可能性</big>
　　就如在構(gòu)型空間中的演算的末尾所提及的，非最優(yōu)解的保留就是為了提供不一樣的演化可能，從而為獲取別的局部或者全局最優(yōu)解保留可能性。
　　在信息空間中，這種保留更體現(xiàn)為這么一種保留——如果一個(gè)基因所蘊(yùn)含的所能生成的圖靈機(jī)中，有些還沒有演化完畢，從而是要么不可停機(jī)的要么能停機(jī)但不能解決任務(wù)的，那么這顯然是非最優(yōu)解。但如果我們將這些非最優(yōu)解都剔除，那么還沒演化到能解決問題的圖靈機(jī)就永遠(yuǎn)不可能演化到能解決問題的那一天——這就是累進(jìn)式演化的本質(zhì)，將暫時(shí)的錯(cuò)誤保留下來，只要剩下的部分能正常工作，留下的錯(cuò)誤在未來就有可能演化出更好的結(jié)果。
　　真實(shí)生物的基因中有很多是無效基因，垃圾基因，要么不產(chǎn)生可表達(dá)的基因序列，要么就是產(chǎn)生了也沒用。
　　但，這些基因難道就應(yīng)該被剔除么？顯然未必如此——其中很多現(xiàn)在無用的基因段，未來完全就有可能在偶然意外的激發(fā)下，從中出現(xiàn)有用的基因。
　　留著現(xiàn)在看來是錯(cuò)誤的東西，就是為了將來能獲得更好的回報(bào)。
　　雖然這種思想在人類社會(huì)中屬于投機(jī)倒把，但，你瞧，奇貨可居其實(shí)也就是一種投機(jī)倒把，而它的結(jié)果是成就了呂不韋與秦嬴政這兩代雄霸。
　　因此，如果演化要保持創(chuàng)造力，那么演化就不能對不夠適應(yīng)的基因趕盡殺絕。

<big>3. 生命的本質(zhì)，就是V與S</big>
　　站在死硬理性派的角度，生命與演化的本質(zhì)與神創(chuàng)一點(diǎn)關(guān)系都沒有，其強(qiáng)大的來源完全是前面所提到的勢能函數(shù)V與演化函數(shù)S——V決定了演化的方向，S決定了如何前往這些方向。而生命，不過是V和S在恰當(dāng)調(diào)配下所得到的結(jié)果。
　　這個(gè)結(jié)論當(dāng)然是充滿了冷冰冰的GEEK感的，想來大家看著也不舒服，特別如果你信教的話——不管拜的是哪位神仙大神。
　　從這個(gè)角度來說，所謂上帝，很有可能不過是為了計(jì)算一個(gè)超級復(fù)雜的問題而設(shè)立的超高級計(jì)算機(jī)程序；而所謂生命，也不過是這段程序跑出來的一個(gè)結(jié)果。
　　這讓我想到多年前我寫的科幻小說了。。。。。。

生命的演化

前面所得到的結(jié)果，當(dāng)然不是無懈可擊的。
　　如果你要站在有神論的角度來反駁攻擊的話，其實(shí)也容易得很。

首先，信息空間本身只蘊(yùn)含所有可計(jì)算的可能性，從而其創(chuàng)造力是可計(jì)算的——于是，第一個(gè)反駁點(diǎn)就是：莎士比亞是可計(jì)算的么？那你給我算一部《哈姆雷特》出來。
　　這個(gè)說法當(dāng)然是糙了點(diǎn)，但問題的本質(zhì)卻是一樣的：上述模型僅僅給出了可計(jì)算的創(chuàng)造力，而人類世界的大量行為大量成果是不可計(jì)算的，甚至很多僅僅只是一種感覺，連可靠定義都沒有，這樣的東西顯然是超出了這個(gè)模型的可論述范圍——從而可能是神創(chuàng)的。
　　而，站在進(jìn)化論的角度，神創(chuàng)者的這種反駁也不是完全沒有反擊的余地——生物分子或者生物官能團(tuán)之間的行為并不單純的是圖靈機(jī)，所以上述模型僅僅是一種類比來給出累進(jìn)式進(jìn)化的強(qiáng)大，并不是說生物就是圖靈機(jī)。既然如此，生物的演化就不會(huì)受到所用模型中圖靈機(jī)只具有可計(jì)算創(chuàng)造力的限制，從而可以實(shí)現(xiàn)不可計(jì)算的創(chuàng)造力。
　　對此，神創(chuàng)論者的進(jìn)一步反駁可以從既然模型并不全然相等因此說生物演化的累進(jìn)式所獲得的創(chuàng)造力完全有可能不足以形成當(dāng)下的人類社會(huì)。
　　這個(gè)問題就瞬間上升到形而上的信仰層面了，因?yàn)槌悄隳芑氐竭^去瀏覽時(shí)間，否則就算理論再完美你依然可以用理論和現(xiàn)實(shí)不是完全匹配的來反駁，于是就成了從一個(gè)不可知來推論另一個(gè)不可知，純粹的信仰問題，不用繼續(xù)爭辯下去了，你信就信，我不信就不信，這事就這么簡單，沒有爭的必要。

第二個(gè)攻擊點(diǎn)比上一個(gè)溫和，那就是累進(jìn)式的O(N log(N))的進(jìn)化步驟所需要消耗的時(shí)間是否能被人類當(dāng)下歷史所容納？
　　這個(gè)問題也是演化支持者很難回答的，因?yàn)镹被預(yù)設(shè)為很大，但是多大算很大呢？完全有可能發(fā)生N log(N)遠(yuǎn)超人類歷史的情況，這么一來，要么歸功于純粹的僥幸，要么歸功于神來之筆的幫助，這事就瞎了。
　　對此，如何估算一個(gè)合理的N是一個(gè)很直面問題但幾乎不可能成功的方案。于是，說到底又成了信仰問題。。。

這么看來，既然無論如何都是信仰問題的話，我只能說，現(xiàn)階段其實(shí)這套模型這套理論依然無法說是完全證明了進(jìn)化論或者說是證明了達(dá)爾文，只能說是提供了一套看上去很不錯(cuò)的理論模型框架。

而，如果我們糾結(jié)一下蔡汀本人的態(tài)度的話，他的態(tài)度是既說自己不算無神論，又各種暗示他的上帝是數(shù)學(xué)。
　　這個(gè)其實(shí)蠻呵呵的。
　　這里岔開一下。多年以前和北京的集智俱樂部的成員有過一次爭論。他們認(rèn)為圖靈機(jī)尤其是Y算子體現(xiàn)了某個(gè)（上位）觀測者的存在；而我的觀點(diǎn)是：這不過就是數(shù)學(xué)。站在蔡汀的角度，這個(gè)爭論倒是沒有必要了，我們在討論的恰好在他看來是同一樣?xùn)|西。

當(dāng)然，我所關(guān)注的倒不是這貨對神創(chuàng)論者有多大沖擊——不管你是告訴我我是從猴子累進(jìn)演化而來的還是告訴我我是克蘇魯捏出來的，反正我都沒差，我還是我。
　　我所關(guān)心的是另一個(gè)層面的問題——生命是什么，生命的演化會(huì)如何走下去。

人擇演化，與，進(jìn)一步演化

從前面的分析我們可以看到，生命不過是V與S的結(jié)果，僅此而已。

這個(gè)命題其實(shí)蘊(yùn)含了很多可以討論的東西，比如，人擇原理就冒了出來，進(jìn)一步演化的方向也冒了出來。

人擇原理

人擇原理有很多版本，最常見的幾個(gè)版本人擇原理是這樣的：

弱人擇原理：宇宙偏愛演化出碳基智慧生物的狀態(tài)。
　　強(qiáng)人擇原理：宇宙的演化必然允許人類的出現(xiàn)。
　　最終人擇原理：宇宙的演化必然導(dǎo)致人類出現(xiàn)，且一旦出現(xiàn)就不會(huì)消失。

當(dāng)然，個(gè)人比較喜歡的人擇原理的版本是這樣的：

我們所在的宇宙為什么允許我們這樣的生物被演化出來？因?yàn)槿绻辉试S的話，就不會(huì)有人在這里提這個(gè)問題了。

這個(gè)問題非但在宇宙學(xué)與粒子物理中存在，對生物進(jìn)化也一樣適用——為何人類能在地球上演化出來？
　　我們都知道，人類的演化是充滿隨機(jī)性的，比如如果當(dāng)年恐龍不被一塊板磚砸死，說不定就沒人類鳥事了。
　　而，這樣的事實(shí)如果我們沿用人擇原理的話，就成了要么恐龍偏愛被一塊板磚砸死，要么恐龍必然會(huì)被一塊板磚砸死。而人的出現(xiàn)則如上帝的選民一般充滿了必然性或者偏愛情。
　　這樣沒節(jié)操的自戀我是無法接受的。

讓我們來對比一下。
　　宇宙可以進(jìn)化出人類，與生物可以進(jìn)化出人類，其實(shí)是兩件非常類似的事情——一樣都充滿了各種僥幸與隨機(jī)。
　　如果說人類在地球上被進(jìn)化出是一個(gè)隨機(jī)事件，那么宇宙中物理參數(shù)可以組合出人類的存在，也是一個(gè)隨機(jī)事件——反之，如果宇宙人擇，那么恐龍必須被一塊板磚拍死，這是上帝的質(zhì)疑，物理的規(guī)律，不可避免——哦，這是瞎扯淡。當(dāng)然，站在神創(chuàng)的角度，這倒的確是必然。
　　因此，人擇原理所反映出的，其實(shí)就是人的一種“選民心態(tài)”，或者說是“人類中心論”。
　　宇宙為何一定要有人類出現(xiàn)？就如地球上為何一定要進(jìn)化出人類一樣，僅僅是一個(gè)概率問題。
　　那么，讓我們更進(jìn)一步——我們已經(jīng)知道，進(jìn)化并不是單線程的，而是多線程的——多路并進(jìn)，且每一路都充滿了備而無用的垃圾基因，而恰恰就是這些垃圾基因，其中有些在漫長的時(shí)間出恰好進(jìn)化出了人所需要的那些生物特征，最后產(chǎn)生了人類。
　　這里的核心有兩點(diǎn)：多線程，攜錯(cuò)。
　　那么，宇宙是否如此呢？

要說宇宙的多線程，這事倒是很好理解——多宇宙。
　　讓我們試想，如果宇宙只有一個(gè)，那么一旦演化錯(cuò)了，那也就不存在人類了——當(dāng)然，現(xiàn)在的你不會(huì)遇到這個(gè)問題，因?yàn)槿绻龅?，也就不存在現(xiàn)在的你了，而一個(gè)不存在之人當(dāng)然不可能思考“我為何不存在”這個(gè)問題了。
　　而，如果宇宙不是單一的，而是復(fù)數(shù)的，甚至是不可數(shù)的，那么這事就有趣了——終將有一個(gè)宇宙的參數(shù)“恰好”合適，誕生出人類。
　　這就和此前的演化模型一樣，多路并進(jìn)，總有一款適合你。
　　而且，從物理上來說，兩者的確足夠相似——信息空間對應(yīng)希爾伯特空間，圖靈機(jī)對應(yīng)宇宙波函數(shù)及其量子化后的產(chǎn)生湮滅算子（理論上所謂的三次量子化或者說宇宙量子化、時(shí)空量子化），演化的目標(biāo)就是來一個(gè)人類冒傻氣。
　　你看，從這個(gè)角度來看，生命的演化和物理的演化是多么類似啊。
　　當(dāng)然，要說差別也有，那就是自然常數(shù)與物理定律不可能改變（也許），所以不存在累進(jìn)式演化，從而致使一個(gè)自然選擇過程。
　　當(dāng)然，我們也可以更激進(jìn)一點(diǎn)，認(rèn)為自然常數(shù)和物理定律也是可以改變的（比如萊姆在《新宇宙演化論》中提出的，也比如《獵戶座防線》），從而也就存在了某種意義上的自然演化。

因而，從這個(gè)角度來說，什么是人擇原理？
　　宇宙的人擇原理，就是在多宇宙中演化出我們這樣的人類的一個(gè)自然選擇／演化過程。
　　而生物的人擇原理，就是在地球上演化出我們這樣的人類的一個(gè)累進(jìn)式自然演化過程。

因此，個(gè)人一貫認(rèn)為對于人擇原理的爭論很無聊。。。

進(jìn)一步演化

我們除了可以將宇宙看作是某種意義上的圖靈機(jī)，還存在另外一些東西也可以這么來看待。

事實(shí)上，如果將生命看作是V與S的結(jié)果，即一切能描述成一個(gè)信息空間中V與S的過程的系統(tǒng)都能視為生命——蔡汀在書中討論過，生命可以被看作是具有演化能力的一種模式。
　　從這個(gè)意義上來說，純數(shù)學(xué)上的圖靈機(jī)當(dāng)然也可以被視為生命了——我們就是利用圖靈機(jī)來論證演化的啊！
　　進(jìn)一步，人工智能，如果存在的話，當(dāng)然也可以被視為生命。
　　甚至于，我們可以更加激進(jìn)地?cái)U(kuò)大化地認(rèn)為，模因也是一種基因，從而社會(huì)乃至科技都可以視為生命。
　　這些東西又將如何演化呢？

這么一看，V與S的演化問題不單單包括了生命的論題，也包括了宇宙、社會(huì)、科技，以及，人工智能為代表的超人。

那么，這些東西的出現(xiàn)是否如人擇所說的一般是一種必然或者偏好呢？
　　這倒是不重要。

重要的是——

<big>下一步，路在何方？</big>

請看幾年前寫的：《演化之路》。

卷尾語

終于寫完這篇東西了，呼呼～～

一本正經(jīng)說《證明達(dá)爾文》這本書的倒是沒幾行字，哎……

前面的內(nèi)容還敢自稱比較硬，最后的一部分，這個(gè)，似乎是水了點(diǎn)。
　　找個(gè)機(jī)會(huì)寫個(gè)續(xù)章，就最后的幾個(gè)問題好好展開一下，應(yīng)該很有意思。

如果你覺得這篇東西寫得還行，愿意打賞我一口咖啡，請戳打賞頁～～
本文遵守創(chuàng)作共享CC BY-NC-SA 3.0協(xié)議**