本文關(guān)鍵詞：細(xì)胞自動(dòng)機(jī)，由筆耕文化傳播整理發(fā)布。

標(biāo)簽：style   blog   http   ext   com   width   

另類(lèi)科學(xué)的核心技術(shù)是細(xì)胞自動(dòng)機(jī)。

烏爾姆（Stanislaw M. Ulam）和馮·諾伊曼（John von Neumann）為了研究機(jī)器人自我復(fù)制的可能性，在上個(gè)世紀(jì)50年代提出一種叫做細(xì)胞自動(dòng)機(jī)(Cellular Automaton)的離散型動(dòng)力系統(tǒng)（Discrete Dynamical Systems）。細(xì)胞自動(dòng)機(jī)是研究復(fù)雜系統(tǒng)行為的理論框架之一，也是人工智能在這個(gè)領(lǐng)域的雛形之一。

在一個(gè)平面上（這里以平面為例，但不限于二維平面）縱橫相交的多條直線(xiàn)構(gòu)成了許多網(wǎng)格，每一個(gè)網(wǎng)格被看作一個(gè)細(xì)胞。這些細(xì)胞可以具有一些特征狀態(tài)，譬如被染成不同顏色。在每個(gè)特定的時(shí)刻每個(gè)細(xì)胞只能處于一種特征狀態(tài)。隨著計(jì)算機(jī)迭代計(jì)算過(guò)程的進(jìn)行，全體細(xì)胞各自根據(jù)周?chē)?xì)胞的狀態(tài)，按照相同的規(guī)則同時(shí)自動(dòng)改變它本身的狀態(tài)，這就構(gòu)成了一臺(tái)細(xì)胞自動(dòng)機(jī)。

決定一臺(tái)細(xì)胞自動(dòng)機(jī)的先決條件有四個(gè)：1、決定細(xì)胞活動(dòng)的空間維度，譬如一維的、二維的或三維的，等等；2、定義細(xì)胞可能具有的狀態(tài)；3、定義細(xì)胞改變狀態(tài)的規(guī)則；4、設(shè)定細(xì)胞自動(dòng)機(jī)中各細(xì)胞的初始狀態(tài)。

1982年Wolfram發(fā)表了第一篇關(guān)于細(xì)胞自動(dòng)機(jī)的學(xué)術(shù)論文，由此開(kāi)始了對(duì)細(xì)胞自動(dòng)機(jī)的研究。Wolfram著重研究空間維度為二維的細(xì)胞自動(dòng)機(jī)。細(xì)胞可能具有的狀態(tài)只有兩種，用顏色表示成黑色或白色。全體細(xì)胞中的每一個(gè)只根據(jù)上一迭代過(guò)程中與該細(xì)胞緊相鄰的三個(gè)細(xì)胞的狀態(tài)來(lái)決定自己下一步的狀態(tài)，所有細(xì)胞在根據(jù)上一步結(jié)果確定自己在這一步中將有的狀態(tài)后，全體細(xì)胞同時(shí)改變自己的狀態(tài)到新?tīng)顟B(tài)。其結(jié)果和細(xì)胞自動(dòng)機(jī)的初始條件很有關(guān)系。被這樣設(shè)定的細(xì)胞自動(dòng)機(jī)叫做一維細(xì)胞自動(dòng)機(jī)。

科學(xué)的道路來(lái)不得半點(diǎn)虛偽和驕傲。這沒(méi)錯(cuò)。但是，如果你的切入點(diǎn)選對(duì)了，也許你在一條新的路上可以成為先行者，而并不一定要先把自己的知識(shí)的背囊裝的滿(mǎn)滿(mǎn)的之后才去開(kāi)始攀登科學(xué)高峰的步伐。Wolfram就是一個(gè)好例子。雖然他確是很聰明，但按照他現(xiàn)在發(fā)表的成果看來(lái)，他15歲就能發(fā)表論文，不完全因?yàn)樗菚r(shí)候有多么淵博的學(xué)問(wèn)，更有可能是因?yàn)樗x了一個(gè)很好的切入點(diǎn)。

下面為你設(shè)計(jì)實(shí)現(xiàn)了一臺(tái)最簡(jiǎn)單的細(xì)胞自動(dòng)機(jī)，請(qǐng)你親手來(lái)做一下。這是學(xué)習(xí)的最好方式，同時(shí)也可以體驗(yàn)到，有時(shí)候進(jìn)入研究最前沿也不是那么高不可攀的事情。我這里說(shuō)的是“進(jìn)入”�？绯鲞@一步后，到你做出成果來(lái)，就會(huì)有無(wú)數(shù)的書(shū)本等著你去翻開(kāi)，有無(wú)數(shù)的實(shí)驗(yàn)等著你去完成，有一段很長(zhǎng)的距離要走。但是你已經(jīng)入門(mén)了。你享受門(mén)外漢不可能體驗(yàn)的樂(lè)趣，你在科學(xué)的某一條小路上攀登著并沿途拿自己的幼稚和汗水去交換路邊的小石、頭頂?shù)囊盎�。不知不覺(jué)間，你就登上了一座小山包，背上的背包已經(jīng)有點(diǎn)重了。俯視走過(guò)的路，自豪與快樂(lè)溢于心間。而前面總有更美的景色在召喚你前行……

下面的例子不需要使用計(jì)算機(jī)，我們用手畫(huà)圖來(lái)完成這個(gè)簡(jiǎn)單的細(xì)胞自動(dòng)機(jī)。請(qǐng)你親手來(lái)畫(huà)一下：

想象有一根無(wú)限長(zhǎng)的線(xiàn)，線(xiàn)上布滿(mǎn)可以變色的點(diǎn)，每個(gè)點(diǎn)的顏色或黑或白。初始條件可以簡(jiǎn)單設(shè)為除一個(gè)黑點(diǎn)外其余的點(diǎn)全白，或者設(shè)為黑白相間。我們按照黑、白相間的簡(jiǎn)單起始規(guī)則，畫(huà)出下圖中的‘起始圖’部分。

起始    ○ ● ○ ● ○ ● ○ ● ○ ● 

然后對(duì)所有的點(diǎn)施行應(yīng)用某種規(guī)則，比如最近鄰規(guī)則：對(duì)線(xiàn)上任意一點(diǎn)，如果在該點(diǎn)最右側(cè)及最左側(cè)的點(diǎn)均為黑色，，而該點(diǎn)本身為白色，則把該點(diǎn)變成黑點(diǎn)。否則該點(diǎn)就保留或改變成白點(diǎn)。

按照上述規(guī)定反復(fù)迭代，就得到了下面的迭代圖的全體。

我們從‘起始圖’開(kāi)始來(lái)推導(dǎo)出‘第一步迭代圖’，請(qǐng)拿一張紙一支筆自己動(dòng)手畫(huà)一畫(huà)：‘起始圖’中的第一個(gè)點(diǎn)是白點(diǎn)，按照迭代規(guī)定，這個(gè)點(diǎn)在‘第一步迭代圖’中保留原來(lái)的白色；‘起始圖’中的第二個(gè)點(diǎn)是黑點(diǎn)，根據(jù)規(guī)定它將在‘第一步迭代圖’中改變成白色；‘起始圖’中的第三個(gè)點(diǎn)的最右側(cè)及最左側(cè)的點(diǎn)均為黑色，而該點(diǎn)本身為白色，故把該點(diǎn)變成黑點(diǎn)畫(huà)在‘第一步迭代圖’中……，依此把‘起始圖’中所有的點(diǎn)檢查一遍，并記住所有點(diǎn)在‘第一步迭代圖’中的新顏色，然后就按照得到的全體點(diǎn)的結(jié)果，畫(huà)出‘第一步迭代圖’。

起始               ○ ● ○ ● ○ ● ○ ● ○ ●

第一步迭代      ○ ○ ● ○ ● ○ ● ○ ● ○

現(xiàn)在針對(duì)‘第一步迭代圖’，按照同樣的方法畫(huà)出‘第二步迭代圖’，‘第三步迭代圖’，……，等等，如下圖所示：

起始             ○ ● ○ ● ○ ● ○ ● ○ ●

第一步迭代    ○ ○ ● ○ ● ○ ● ○ ● ○

第二步迭代    ○ ○ ○ ● ○ ● ○ ● ○ ● 

第三步迭代    ○ ○ ○ ○ ● ○ ● ○ ● ○ 

由圖中可以看到，每迭代一次，白點(diǎn)就向右側(cè)移動(dòng)一位。這樣就得到了一個(gè)點(diǎn)的動(dòng)態(tài)移動(dòng)的模式。

怎么樣？簡(jiǎn)單吧？你剛剛做了一臺(tái)細(xì)胞自動(dòng)機(jī)哪！

請(qǐng)你在這里暫停閱讀并想一想在計(jì)算機(jī)上實(shí)現(xiàn)這個(gè)簡(jiǎn)單的一維細(xì)胞自動(dòng)機(jī)的情景。能替它找到一些相關(guān)的應(yīng)用嗎？

我找了幾個(gè)如下：

如果在計(jì)算機(jī)上實(shí)現(xiàn)上述的簡(jiǎn)單一維細(xì)胞自動(dòng)機(jī)，并在一根直線(xiàn)上畫(huà)出每次的迭代過(guò)程，就可以看到一個(gè)白點(diǎn)向右側(cè)運(yùn)動(dòng)的動(dòng)態(tài)過(guò)程。如果把直線(xiàn)畫(huà)成螺旋狀，這個(gè)點(diǎn)就會(huì)沿螺旋運(yùn)動(dòng)。如果畫(huà)成環(huán)狀，點(diǎn)就沿著環(huán)跑個(gè)不停。

如果只把圖中改變顏色的點(diǎn)畫(huà)出來(lái)，并且把點(diǎn)畫(huà)成宇宙飛船的形狀而不是圓點(diǎn)的形狀，直線(xiàn)畫(huà)成某種空間軌跡。那么在程序運(yùn)行時(shí)，就得到了一艘宇宙飛船沿軌跡飛行的動(dòng)態(tài)畫(huà)面。如果畫(huà)兩艘敵對(duì)的宇宙飛船并設(shè)計(jì)它們的相撞的軌跡，就可以得到一個(gè)簡(jiǎn)單的星球大戰(zhàn)的游戲。

怎么樣？挺好玩的吧？您再想點(diǎn)別的花樣？

下面是一個(gè)從《另類(lèi)科學(xué)》中取來(lái)的、更具體的、也更復(fù)雜一點(diǎn)的例子。如果您有耐心又有興趣的話(huà)，通過(guò)它可以更深入了解Wolfram的工作的基本原理。如果沒(méi)有興趣，就跳過(guò)去不讀它即可。作者的饒舌是自己興之所至的塗鴉，讀者大可不必跟著給弄得暈頭轉(zhuǎn)向。當(dāng)然如果我的作品有這么大的魔力讓你跟著我的思想轉(zhuǎn)悠，我會(huì)很有成就感的。謝謝了。

考慮并排的三個(gè)格子，它們分別被賦予黑白兩種狀態(tài)。考慮各種可能的排列方式，我們不難得到共有8種組合狀態(tài)。這8種組合狀態(tài)的每一種都各自決定下一個(gè)細(xì)胞是黑色或白色，這樣算下來(lái)的排列總共有256種可能性。因此在Wolfram考慮的細(xì)胞自動(dòng)機(jī)種類(lèi)中，細(xì)胞改變狀態(tài)的規(guī)則有256種。Wolfram把這256種規(guī)則一一編號(hào)。譬如下面的圖就代表110號(hào)規(guī)則：

圖9-4 Wolfram的細(xì)胞自動(dòng)機(jī)110號(hào)規(guī)則

用文字來(lái)敘述就是：當(dāng)某細(xì)胞的上一行相鄰三個(gè)細(xì)胞為全黑、全白或者左側(cè)一個(gè)細(xì)胞為黑時(shí)，該細(xì)胞為白色，否則為黑色。設(shè)定一個(gè)簡(jiǎn)單的細(xì)胞初始狀態(tài)，譬如在第一行只有一個(gè)黑色細(xì)胞，根據(jù)規(guī)則110，細(xì)胞自動(dòng)機(jī)就可以自動(dòng)把其余的細(xì)胞變成黑色或保留白色。下圖就是根據(jù)規(guī)則110運(yùn)行了前20步的情況，在這里似乎看不出什么有趣的東西。但運(yùn)行到幾百步后，就出現(xiàn)了一些有趣的特征，一些結(jié)構(gòu)開(kāi)始既不是周期性地也不是完全隨機(jī)地出現(xiàn)在畫(huà)面上。下圖是按規(guī)則110運(yùn)行到700步的情況。

圖9-5 110號(hào)規(guī)則運(yùn)行了前20步的情況                  圖9-6 110號(hào)規(guī)則運(yùn)行了前700步的情況

從上面的兩個(gè)例子中我們可以看到，在這樣的模式中，確實(shí)沒(méi)有用到經(jīng)典的數(shù)學(xué)公式。

Wolfram用類(lèi)似的方法，得到了除量子力學(xué)外經(jīng)典物理學(xué)中的所有公式。

也就是說(shuō)，不用數(shù)學(xué)公式也可以借助計(jì)算機(jī)來(lái)描述自然界。不用數(shù)學(xué)公式也可以借助計(jì)算機(jī)來(lái)研究宇宙。

1984年Wolfram把256種規(guī)則分成了四類(lèi)：第一類(lèi)只生成簡(jiǎn)單重復(fù)的圖案，比如全黑、全白、或黑白相間如國(guó)際象棋棋盤(pán)等等；第二類(lèi)規(guī)則產(chǎn)生一些自相似的分形圖案，形成穩(wěn)定的嵌套結(jié)構(gòu)；第三類(lèi)規(guī)則產(chǎn)生的圖案具有明顯的隨機(jī)性；第四類(lèi)規(guī)則產(chǎn)生復(fù)雜的圖案，但不簡(jiǎn)單重復(fù)。

這些圖案既不是規(guī)則的也不是完全隨機(jī)的。它們呈現(xiàn)出某種有序性，但卻不能被預(yù)言。

Wolfram關(guān)注較多的是第四類(lèi)規(guī)則。第110號(hào)規(guī)則及30號(hào)規(guī)則是第四類(lèi)規(guī)則中的精粹。通過(guò)它們可以從簡(jiǎn)單的初始條件產(chǎn)生出復(fù)雜的圖形。這是Wolfram對(duì)細(xì)胞自動(dòng)機(jī)理論所做出的巨大貢獻(xiàn)。

Wolfram所用的軟件計(jì)算本身并不復(fù)雜，復(fù)雜的是怎樣處理輸出結(jié)果。有了適當(dāng)?shù)能浖�，就可以開(kāi)展對(duì)細(xì)胞自動(dòng)機(jī)的研究。

Cited from：?mod=space&uid=1235952&do=blog&id=232854

Note：cellular automaton 通過(guò)對(duì)問(wèn)題進(jìn)行編碼使其更加直觀，可以表示傳統(tǒng)方法難以表達(dá)的特征。 比如展示同源 nucleotide sequence 之間的差別，可以將一維的序列轉(zhuǎn)化為二維的數(shù)組，然后將數(shù)組以圖像的形式反映出來(lái)，于是將序列的特征反映到二維圖像上，可以用直觀的方式發(fā)現(xiàn)其特征。

細(xì)胞自動(dòng)機(jī)【轉(zhuǎn)】,布布扣,bubuko.com

細(xì)胞自動(dòng)機(jī)【轉(zhuǎn)】

標(biāo)簽：style   blog   http   ext   com   width   

  本文關(guān)鍵詞：細(xì)胞自動(dòng)機(jī)，由筆耕文化傳播整理發(fā)布。