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

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

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

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

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

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

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

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

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

下面的例子不需要使用計(jì)算機(jī)，我們用手畫圖來完成這個(gè)簡單的細(xì)胞自動機(jī)。請你親手來畫一下：

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

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

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

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

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

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

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

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

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

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

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

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

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

怎么樣？簡單吧？你剛剛做了一臺細(xì)胞自動機(jī)哪！

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

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

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

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

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

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

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

圖9-4 Wolfram的細(xì)胞自動機(jī)110號規(guī)則

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

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

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

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

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

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

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

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

Wolfram所用的軟件計(jì)算本身并不復(fù)雜，復(fù)雜的是怎樣處理輸出結(jié)果。有了適當(dāng)?shù)能浖螅涂梢蚤_展對細(xì)胞自動機(jī)的研究。

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

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

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

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

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

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