# 細胞自動機 (Cellular Automata )

## Presentation on theme: "細胞自動機 (Cellular Automata )"— Presentation transcript:

Sierpinski's Triangle Sierpinski's Triangle is a very famous fractal that's been seen by most advanced math students. This fractal consists of one large triangle, which contains an infinite amount of smaller triangles within. The infinite amount of triangles is easily understood if the fractal is zoomed in many levels. Each zoom will show yet more previously unseen triangles embedded in the visible ones. Creating the fractal requires little computational power. Even simple graphing calculators can easily make this image. The fractal is created pixel by pixel, using random numbers; the fractal will be slightly different each time due to this. Although, if you were to run the program repeatedly, and allow each to use an infinite amount of time, the results would be always identical. No one has an infinite amount of time, but the differences in the finite versions are very small. To generate this fractal, a few steps are involved. First, initial X and Y values should be chosen, either by the program or the user. The values used have little effect on the fractal. Regardless of what's chosen, the same triangle will be created. Next, the program must create a random number, between 0 and 1. Then, three possible routes can be taken.

If the random number is less then 1/3, then the following equations should be applied to X and Y.
xn = 0.5 * (xn-1 + 1) yn = 0.5 * yn-1 If the random number is between 1/3 and 2/3, then these equations should be used. xn = xn-1 * 0.5 yn = yn-1 * 0.5 If the number is greater than 2/3, the the following equations should be applied. xn = 0.5 * (xn ) yn = 0.5 * (yn-1 + 1) Now that X and Y have changed, the point should be plotted on the screen. Finally, loop back to the random number generation and start over again. Only a few hundred iterations are needed to begin to see the triangles. A few thousand pixels will produce a good image.

Sierpinski's Triangle

1926年 Von Neumann 以一篇集合論的論文獲得布達佩斯大學的博士學位，然後以 Rockefeller 獎學金前往哥廷根大學跟隨 Hilbert 作博士後研究，並在柏林，漢堡講學。Von Neumann 在廿餘歲時已經是數學圈中公認的年輕天才。 1930年 Von Neumann 應 Veblen 之邀，到普林斯頓大學客座，1931年普林斯頓大學即授予教授職位，1933年他成為新成立的普林斯頓高等研究院終身職院士。Von Neumann 的家庭宴會在普林斯頓非常熱鬧知名，這在數學家中是很少見的。

（5）Ergdic（遍歷性）定理的証明（1938）。

Cellular Automata and Complexity: Collected Papers
by Stephen Wolfram Are mathematical equations the best way to model nature? For many years it had been assumed that they were. But in the early 1980s, Stephen Wolfram made the radical proposal that one should instead build models that are based directly on simple computer programs. Wolfram made a detailed study of a class of such models known as cellular automata, and discovered a remarkable fact: that even when the underlying rules are very simple, the behavior they produce can be highly complex, and can mimic many features of what we see in nature. And based on this result, Wolfram began a program to develop what has become A New Kind of Science. The results of Wolfram's work found many applications, from the so-called Wolfram Classification central to fields such as artificial life, to new ideas about cryptography and fluid dynamics. This book is a collection of Wolfram's original papers on cellular automata and complexity. Some of these papers are widely known in the scientific community; others have never been published before. Together, the papers provide a highly readable account of what has become a major new field of science, with important implications for physics, biology, economics, computer science and many other areas. Published (1994): ISBN (hardcover) ISBN (paperback)

1 、 網格（cells ） CA 是由一組的網格（或稱細胞）所構成。理論上這些網格可以是任何幾何形狀，甚至可以立體的單元，不過目前大部分的CA 研究都是以規則排列的方格為主，其空間結構和網格式資料模式的結構相同，及為一2維的矩陣。 2 、 網格狀態（states ） 每一個網格的內容是由一組有限的狀態來顯示，這些狀態的值域可以是二元的（Binary），如：活的、死的；空的（NULL）、已經被佔據的。也可以是多元的類別集合，例如：建地、空地、商業用地、住宅用地等土地利用類型。狀態，亦可以是實數或等第尺度的值域。在任一時間，每一個網格都將呈現這一組狀態中的唯一特定值。

3 、 鄰近區(neighborhood) CA 中每一個網格的狀態，會隨著其鄰近地區內的網格狀態來進行變化。設計一個CA 時需要界定其會相互影響的鄰近區大小。以網格式的資料結構而言，鄰近區可以是中心網格最近的周遭網格或一定距離內的所有網格。 4 、 演化規則 每一個網格在下一個時間點的狀態，是由其目前的型態及其鄰近區內網格對此網格影響的總組合而決定。由一條條明確的規則決定下一時間點型態的演變。在上述的時空結構下，CA 的演化循環是在一個離散的（discrete ）時間序列下（… ,t-1, t, t+1, …），所有網格依據演化規則進行同步更新。

Rule table: (GKL CA) Lattice: r = 1 1 1 1 1 1 1 t=0 t=1 1 1 1 1 1 1 t=2 1 1 1 1 1 1

Cellular Automata Tutorial
Cellular Automata Gallery Mirek's Java Cellebration v.1.50  Modern Cellular Automata George Maydwell's Cellular Automata Page Home of SARCASim 一維細胞自動機，與其規則（一） 一維細胞自動機的有趣範例 細胞自動機和音樂 相關連結與資源

game of Life (生命遊戲) 數學家康威(John Horton Conway)在 1970年發明稱之為 game of Life(生命遊戲)的細胞自動機，他把平面(即二維的空間) 分割成很多方格子(類似圍棋棋盤)，每一格子為一細胞，每一細胞有八個鄰居，細胞有兩種狀態，“生” 或 “死”( 在電腦裡可以 1 或 0 來代表)，細胞自動機的規則如下： 1. 活細胞如果有二或三個鄰居則可以活到下一世代, 否則就會死於獨居或壅擠 。 2. 死細胞處如果恰好有三個活細胞鄰居，則可生出活細胞 ( 就某種意義上來說可視之為"繁殖")。

A dead cell with exactly three live neighbors becomes a live cell (birth).

A live cell with two or three live neighbors stays alive (survival).

In all other cases, a cell dies or remains dead (overcrowding or loneliness).

Conway's Game of Life

Online Game of Life The Game of Life is not your typical computer game. It is a 'cellular automaton', and was invented by Cambridge mathematician John Conway. This game became widely known when it was mentioned in an article published by Scientific American in It consists of a collection of cells which, based on a few mathematical rules, can live, die or multiply. Depending on the initial conditions, the cells form various patterns throughout the course of the game.

game of Life http://serendip.brynmawr.edu/complexity/life.html
Modern Cellular Automata The Virtual cellular automaton - You better come on in my kitchen. It's going to be raining outdoors. -- Robert Johnson

Langton’s Ants 1. The ant takes a step forward
2. If the ant is now standing on a white point, then it paints the point black and turns 90 degrees to the right. 3. Otherwise, if the ant is standing on a black points, then it paints it white and turns 90 degrees to the left. Eight steps of Langton’s virtual ant, starting from an initially blank grid.

Langton's Ants

Langton's Ant

Langton's ant

ｅ蟻雄兵 誰說大腦發達的生物才聰明？頭腦簡單的螞蟻不但能建構驚人的地下蟻城，還將掀起一場人類電腦科技革命！

simple ant farm http://www.acme.com/software/xantfarm/
There are three Elements in the ant world: Air, Dirt, and Sand. Ants move through Air, dig up Dirt, and drop it as Sand. Ants have three Behaviors: Wandering, Carrying, and Panic. There are a few simple probabilities built in to the program that control the transitions between Wandering and Carrying. To see them Panic, try poking the ants with the cursor.

Stephen Wolfram Cellular Automata as Simple Self-Organizing Systems (1982)

Cellular Automata + MIMD Parallel Computers
= CAMEL and CARPET

Cellular Automata

Artificial Life

Darwin Pond Darwin Pond is an imaginary gene pool, a primordial puddle of genetic surprises. More technically, Darwin Pond is an Artificial Life Simulation: a virtual world exhibiting the emergence of life-like behaviors. But it's more than just a fun and informative thing to watch, you can participate in this artificial life simulation by building little scenarios and setting up experiments.

(Artificial Intelligent)
人工智慧 AI (Artificial Intelligent)