看板 Cognitive 關於我們 聯絡資訊
簡明介紹:http://mmdays.com/2007/07/12/game_of_life/ 簡單模擬:http://www.bitstorm.org/gameoflife/ 更多例子: 網址:http://www.atlas-zone.com/complex/alife/ca/index.html 細胞自動機 Cellular Automata 2002, 1, 10 吳文成   細胞自動機(Cellular Automata)最初由數學家 Stanislaw M. Ulam(1909-1984) 與 John von Neumann(1903-1957)於 1950 年代所提出 ,在型態表現上,細胞自動機 是一個離散型的動力系統( Discrete Dynamical Systems)。在 1940 年代 ,von Neumann 與共事的科學家們合作設計了可儲存程式的數位電腦之後,他就對自我複製發生 興趣:能儲存程式的機器能不能自我複製 ? von Neumann 認為,至少在原則上與形式上是可行的,於是他開始作這方面的理論研 究,過程中他提出了「細胞自動機」的概念, 這個實際構想是由羅沙拉摩斯的數學家 Ulam 所建議的 。當細胞自動機在電腦上模擬的時候,幾乎可以複製出類似於自然界當中實際發生的動力 系統運作,這使得細胞自動機成為了研究複雜系統行為的最初理論框架,羅沙拉摩斯的博 士後研究員 Christopher Langton 因而提出了「人工生命」( Artificial Life )這個 名詞 , 細胞自動機便是人工生命的第一個雛形,並且變成複雜性科學,或者說是複雜適 應性系統的其中一支。   細胞自動機是由一些特定規則的格子所組成,每個格子看做是一個細胞;每一個細胞 可以具有一些狀態,但是在某一時刻只能處一種狀態之中。隨著時間的變化(我們稱作「 疊代」過程),格子上的每一個細胞根據周圍細胞的情形,按照相同的法則而改變狀態, 換句話說,一個細胞的狀態是由上一個時刻所圍繞的細胞的狀態所決定。以人工生命的角 度來看,細胞自動機可以視為一個讓許多單細胞生物生活的世界,在我們設定好這個世界 的初始狀態之後,它們便按照同一個規則做演化。   設計一個細胞自動機需要包含幾個部份:   ◆ 決定細胞活動空間的維度   ◆ 定義細胞可能具有的狀態   ◆ 定義細胞改變狀態的規則   ◆ 設定細胞自動機中各個細胞的初始狀態   細胞自動機,在細胞活動的空間上,可以是一維的,二維的,三維的,或更高維度, 在這個網頁,筆者要分別介紹二維的細胞自動機(也稱作「生命遊戲」),與一維的細胞 自動機。透過不同的設計,細胞自動機可以展現無限的多樣性,其中最讓人驚異的是有些 細胞自動機可以產生存在於大自然的景象,例如貝殼上的圖案、雪花的結構、蜿蜒的河流 等等,另外,我們也可以發現,這些小方格的變化似乎展現了許多真實生命的特質,例如 ,細胞自動機中的細胞們會像有機生物一般,有移動、成長、滅亡與自我複製等類似的行 為。   就形式而言,細胞自動機有三個特徵:   ◆ 平行計算(parallel computation):每一個細胞個體都同時同步的改變   ◆ 局部的(local):細胞的狀態變化只受周遭細胞的影響。   ◆ 一致性的(homogeneous):所有細胞均受同樣的規則所支配   事實上,有些研究學者更進一步猜測,我們存在的這個宇宙是否就是一種極其複雜的 細胞自動機,我們的宇宙的確與理論上的細胞自動機有很多相似的地方,像是上述的細胞 自動機之三個特徵,宇宙也都符合:宇宙是平行處理的,宇宙中的每一點受鄰近狀態的影 響最大,宇宙各處遵循著同樣的自然律。雖然與整個宇宙相比,細胞自動機的規則是過於 簡單,但是它裡面所蘊含的道理可能與宇宙的機制是相通的。 理論物理學家 Stephen Wolfram(1959-)就指出 ,細胞自動機的數學架構,與一些造成真實世界的複雜物理系 統之數學架構是完全一樣的,也許這正是掌管遺傳重任的 DNA 所賴以工作的原理 。當你 看到自然界那些貝殼或指紋曲折的圖案時,不免要問 :「這麼複雜的圖案要如何編碼到 DNA 裡頭呢?」Wolfram 說 :「如果我猜的不錯,那些圖形是由類似於細胞自動機的簡 單法則所產生的,而這樣的編碼顯然是易如反掌。」   細胞自動機以簡單的規則,卻能夠產生複雜的動態交互現象,顯然我們不該只是以一 個數學遊戲,來看待它。這些年來,細胞自動機已經被運用於不同領域的研究,包括通訊 、計算、建設、生長、再生、競爭及演化。細胞自動機已為物理中平常的微分方程式提供 極為簡單的模型,例如熱和波的波動方程,同時也為湍流、混沌、碎形等提供了離散型的 模型,最後,利用細胞自動機所做的生物模型也被提出。接下來,筆者將盡可能地介紹細 胞自動機的規則、範例與相關資訊,以下的介紹分為兩種不同類型的細胞自動機:   |   ├─ 二維的細胞自動機:   |   |   |   ├─ 生命遊戲,與其規則   |   ├─ 生命遊戲的有趣範例   |   ├─ 生命遊戲的規則變化(一)   |   ├─ 生命遊戲的規則變化(二)   |   ├─ 生命遊戲的規則變化(三)   |   └─ 生命起源於混沌的邊緣   |   ├─ 一維的細胞自動機:   |   |   |   ├─ 一維細胞自動機,與其規則(一)   |   ├─ 一維細胞自動機,與其規則(二)   |   ├─ 一維細胞自動機,與其規則(三)   |   ├─ 一維細胞自動機的有趣範例   |   └─ 四個普遍性等級的再探討   |   └─ 相關連結與資源   瞭解了細胞自動機的疊代過程之後,你會發現:細胞自動機在某一疊代的細胞形態只 會產生「唯一」形態的下一代,而我們卻無法從新一代的形態而回溯得知上一代確定的細 胞形態,因為這樣的「回溯」有太多種可能性,而且可能性的數量會隨著一次接著一次的 「回溯」而以指數比例地增加,這使得我們即使看見某一疊代中有趣的細胞演化,卻無法 準確地推回出它的初始狀態 。這種性質,我們稱呼為「Forward-Deterministic」,意思 是,細胞自動機的疊代演化是往前決定的,它有許多個可能的過去,但是它的未來發展只 有一個,而這個唯一的未來發展所產生的複雜度,卻常常在人們的預期與想像之外。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.229.124.159
sardine:稍微看了一下 我覺得這中間有些小問題.. 04/20 12:25
sardine:一面是數學家把生物想的太簡單了.. 04/20 12:25
sardine:在公理集合論裡面對探討的集合跟邏輯是非常嚴正的 04/20 12:27
sardine:數學家也把一些生物上的序列看的很簡單 就像直線一樣 04/20 12:28
sardine:把生物資訊的特徵值數化量化 做出等量的刻度 04/20 12:28
sardine:之後才能引進數學理論 但這個過程在生物界就有很大的問題 04/20 12:29
sardine:另一面是生物學家也把數學想的太粗糙的 04/20 12:29
sardine:就如同上面所說的嚴正的尺度...1跟1.0000000000000000001 04/20 12:32
sardine:到底一不一樣...差不多一樣在數學上是不被接受的 04/20 12:32
sardine:可是自然界中卻存在很多差很多卻是本質一樣的東西 04/20 12:33
sardine:簡化一個系統也許真的可以看出個什麼特別的隱藏意義 04/20 12:35
sardine:但就如同圖片壓縮檔一樣...從bmp軟成jpeg時已經遺失了大半 04/20 12:36
sardine:的資訊...這些資訊到底重不重要 到底會不會影響推理.. 04/20 12:36
sardine:不是神誰也不知道... 04/20 12:37
sardine:我只是覺得不管他做這種系統的動機為何 04/20 12:37
sardine:中間這段猜想宇宙的機制已經有點變過度的幻想.. 04/20 12:39
cog5566:最近在看一本書也有提到這個,就是天下文化翻譯的理性之夢 04/20 21:22
cog5566:覺得翻成"格狀自動機"比較不會讓人誤會(讓我這種英文爛的) 04/20 21:35
cog5566:我覺得他們會這樣想還滿容易理解的,畢竟科學的一個目標就 04/20 21:37
cog5566:是尋找最萬物最簡單的規則。而格狀自動機就是定義簡單規則 04/20 21:38
cog5566:卻可以模擬出一些生物特性。再加上他是一個平行處理的動態 04/20 21:40
cog5566:系統,而且也遵照局部性。這樣就和我們概念上的宇宙是相同 04/20 21:41
cog5566:性質的。(當然這些性質有沒有定論應該還早。這一期個科) 04/20 21:42
cog5566:學人就在講局部性的爭議)。不過想法就是如果宇宙的時空性 04/20 21:44
cog5566:質,在微觀上是以離散的方式組成的話,格狀自動機就可以模 04/20 21:45
cog5566:擬許多現象。我覺得這個遊戲倒不是真的想要把宇宙模擬的一 04/20 21:49
cog5566:模一樣,而是想要展現一些我們認為是複雜的現象,如生物活 04/20 21:55
cog5566:動,可以由簡單的規則和數位運算的方式創造出來。 04/20 21:56
takanaka:一個有趣的問題是科學的目的何在 04/21 00:36
takanaka:我想多少是在求真與求簡之間找到平衡 04/21 00:37
takanaka:對一個複雜系統的科學解釋必定要比所觀察到的更簡單 04/21 00:38
takanaka:不然一般的結局就是循環解釋或是根本沒解釋 04/21 00:39
takanaka:比方說我們要解釋為什麼我們可以辨識人臉 04/21 00:40
takanaka:一個古老的循環解釋為因something in the head可以辨識 04/21 00:44
takanaka:所以這個問題到底人臉是怎麼被辨識的還是沒有被回答 04/21 00:45
takanaka:儘管scope從人變成something in the head再變成大腦等等 04/21 00:46
takanaka:這是為什麼資訊處理的演算法則通常是被抽象化來分開研究 04/21 00:47
takanaka:因為reduce了physical scope仍未必能回答機制上的問題 04/21 00:48
sardine:求真與求簡的平衡也是數學跟自然界的鴻溝... 04/21 01:10
sardine:我對心理學跟社會科學部份不了解 04/21 01:11
sardine:不過就生物資訊方面 多半的人都希望越簡越好 04/21 01:12
sardine:可是這個簡化的過程並沒有一個標準或公認的定論.. 04/21 01:12
sardine:要一直延伸到組織/細胞層級以下 對標準化的共識才比較深 04/21 01:13
sardine:舉個例來說~在生物的野調上~~樣區邊界半外半內的區域該如 04/21 01:16
sardine:何計量~~~這個只有經驗~並沒有統計標準. 04/21 01:16
sardine:可是對幾百千億萬平方公里的的母群體來說 這種誤差絕對 04/21 01:18
sardine:超過數學上付予機率跟統計可容許的標準 04/21 01:18
sardine:但我在野調時也不怎麼在意這種事... 04/21 01:19
sardine:光是肯定無異議的樣區內~對生物特徵的量化 每個調查員的主 04/21 01:21
sardine:觀意識就已經造成我不太能接受的誤差了.. 04/21 01:21
sardine:只是生態學家似乎不太在意這種事 團隊中的大家長說了就算 04/21 01:22
sardine:在物理/化學對狀態的描述還滿精確的 每種現象背後都有種 04/21 01:25
sardine:強大的趨動力而且幾乎是不可違背的 也經過實驗 (直接證明 04/21 01:26
sardine:or反證) 04/21 01:28
sardine:這種背後的趨動力相對於數學就是公理 04/21 01:28
sardine:不知道在大家的專長對於人類認臉跟人類辨識立體圖象的差別 04/21 01:32
sardine:在哪~~我在辨識物種時常常有很大的困擾 標準是拿來參考 04/21 01:33
sardine:用的~就算DNA序列有95%的相似度~~這樣的數字也是參考用的 04/21 01:34
sardine:在這樣的簡化過程中跟數學的公理就有所違背 04/21 01:36
sardine:對這篇要求的簡 我覺得跟化學家口中的"勢"是一樣的 04/21 01:40
sardine:簡單的說就是一切的狀態會趨向於混頓~~~ 04/21 01:43
sardine:但這個變化的過程有些有趣的徒徑~像將墨水低在水中會單向 04/21 01:44
sardine:的慢慢擴散到均勻~~~但也有某些狀態會程震蕩的狀態 04/21 01:45
sardine:http://ppt.cc/uLTW 像這個 04/21 01:51
sardine:這兩種徒徑跟原文中網頁模擬出的趨向就很相近 04/21 01:52
sardine:可是會讓物化現象跟原文中的趨向程高度相似的原因就是.. 04/21 01:53
sardine:動力論~~ 雖然熱力學中的確有一條是經驗法則 到現在無法 04/21 01:54
sardine:證明 但也未曾有人能提出有力反駁 04/21 01:55
sardine:可是離開了物理化學離開了組織細胞的層次 這種動力論真的 04/21 01:55
sardine:存在嗎 04/21 01:55
sardine:或者說生物的複雜讓人無法簡化他~~舉個例子來說 04/21 01:59
sardine:為什麼冷氣機可以讓熱從低處往高處流~~ 04/21 01:59
sardine:原因是外界所施予的功改變了系統的entropy 而這一切的狀態 04/21 02:01
sardine:改變還是束縛在熱力學這個最強大的動力系統規則下 04/21 02:01
sardine:可是生物上呢本身的形態及天性對生物行為有最大的影響 04/21 02:03
sardine:可是形態是受DNA所束縛的嗎~~只能說多半是 另一半卻是營養 04/21 02:03
sardine:那天性就更難解釋了 04/21 02:04
sardine:而從大家所知的邏輯 若無法確定生物體被後的動力系統規則 04/21 02:05
sardine:那這樣的動力系統最終也只能做為看看課本看看論文後的娛興 04/21 02:07
sardine:節目 04/21 02:07
sardine:或者說對每個生化代謝反應 對每個不同的組織器關 都有一種 04/21 02:08
sardine:還滿有力的動力系統規則 但當千萬種規則共組一個生物體時 04/21 02:09
sardine:每一種規則又沒有先後順序或對個體極突出的影響時 04/21 02:10
sardine:大家都互相抵消互相加成~~那就等於沒有規則了 04/21 02:11
sardine:生物上真的有什麼萬不可逆的規則嗎~~也許有這麼一條.. 04/21 02:12
sardine:沒有ATP就沒有活著的生物 除了這個外其他沒有什麼是沒有 04/21 02:13
sardine:例外的...就像某板的名言..當考題出現"一定""只有""唯一" 04/21 02:13
sardine:這些詞時 九成都是錯的.. 04/21 02:14
sardine:----------------------------------------------------- 04/21 02:15
sardine:另外我很大嘴巴 很愛講話 又特別堅持純數中的嚴正地位 04/21 02:15
sardine:如果我的話有哪些部份會讓人覺的不爽還請包含 04/21 02:16
sardine:如果我的想法有人覺得是錯誤的 還請大家救救我 給我正確的 04/21 02:17
sardine:邏輯觀 04/21 02:17