自我复制的元胞自动机
程序简介
- 名 称： 能自我繁殖功能的细胞自动机
- 作 者： Eli Bachmutsky
- 源 代 码：Self_product.zip
程序运行说明
如果说生命区别于非生命的最本质因素就是自我繁殖的话，用细胞自动机的简单规则演化出来的生命体就能达到生命的这个标准。下面的程序给你揭示了一类细胞自动机根据演化的规则能够把一个结构（在这里都是圈）进行自我复制。你会看到一生二、二生四……的大自然造物的过程。最早研究这个问题的是Von Neumann，当时人们曾经否认机器能够产生生命，就是因为程序不能进行自我复制。于是Von Neumann等人找到了一个巧妙的能够进行自我复制的细胞自动机否定了这个观点，不久以后，第一个计算机病毒诞生了。病毒就是一段能够不断自我繁殖的程序。接下来探讨这个问题的认识Chris Langton，它用细胞自动机研究人工生命这个领域，并且发明了比Von Neumann更巧妙的细胞自动机（下面的程序中的Langton Loop就是这个程序）。接下来又有很多人对程序进行改进，人们运用细胞自动机让程序自动涌现出可复制的结构从而洞悉造物主的意图。
首先，请运行上面的java小程序，如果你的CPU很慢，请耐心等待！
程序说明
可以在下拉列表框里面选择不同的细胞自动机规则，程序将给出不同的初始状态（一个圈）和不同的演化规则，但是它们的共同点是这些圈都会自我复制。按下Start按钮程序自动开始演化，或者按下step按钮程序将在用户控制下一步一步的演化运行。其中不同颜色的方格表示细胞的不同状态，这里面列出的所有细胞自动机的邻居都是上下左右四个Von Neumann类型的邻居。
这些圈的定义与规则如下：其中数字表示不同的状态，规则中第一位表示当前细胞的状态值，接下来的四位为邻居的状态，最后一位表示当前细胞的下一时刻的状态值。
| 圈的类型 | 初始状态 | 演化规则 |
|---|---|---|
| Byl's loop (12 个细胞, 6 个状态) | 22 2312 2342 25 |
000000 000010 000031 000420 000110 000120 000311 000330 000320 000200 000242 000233 004330 005120 001400 001120 001305 001310 001320 003020 003400 003420 003120 002040 002050 002010 002020 002420 002500 002520 002200 002250 002220 040000 050000 050500 010052 010022 010400 010100 020055 400233 405235 401233 442024 452020 415233 411233 412024 412533 432024 421433 422313 501302 502230 540022 542002 512024 530025 520025 520442 523242 522020 100000 100010 100033 100330 101233 103401 103244 111244 113244 112404 133244 121351 123444 123543 122414 122434 300100 300300 300211 300233 304233 301100 301211 303211 303233 302233 344233 343233 351202 353215 314233 311233 313251 313211 312211 335223 333211 320533 324433 325415 321433 321511 321321 323411 200000 200042 200032 200022 200442 200515 200112 200122 200342 200332 200242 200212 201502 203202 202302 244022 245022 242042 242022 254202 255042 252025 210042 214022 215022 212052 212055 212022 230052 234022 235002 235022 232042 232022 220042 220020 220533 221552 |
| Chou/Reggia 1 (6 细胞, 8 状态) | 11 3411 |
000000 000200 000110 004420 006301 001447 003030 046000 060400 062102 051060 010420 010360 012152 032000 401033 410011 431206 640406 660630 616600 636000 000440 000260 000330 004512 005103 001540 003100 045002 060600 061110 051710 010506 010320 030400 076010 460313 410633 600000 640106 610006 616100 636100 000420 000231 000705 006030 002020 001210 040000 045600 060100 050006 020320 010140 016000 036000 400035 466633 410100 606100 660060 610106 613001 676600 000600 000100 004040 006440 001010 001110 040160 041040 060166 050306 024200 010154 016100 036606 400313 423106 411033 606313 660460 614004 630160 500000 000540 000152 004010 006110 001030 003000 044400 060066 062030 054040 023010 010340 012000 036300 405033 410061 431033 640006 660615 616000 630360 500044 500011 230000 100111 101044 146004 143321 166611 121121 117044 300111 340066 366611 374017 200100 100044 104414 101601 141403 160414 161101 112244 130414 304011 340611 314001 703010 203010 100011 104674 101301 141424 160111 161301 111044 133001 301471 340261 314676 703330 240400 100441 106101 103011 141141 164104 120414 113011 133011 301303 340211 313023 733630 210102 100414 105011 103103 141121 166644 124104 113601 300101 307141 344011 331001 |
| Chou/Reggia 2 (5 细胞, 8 状态) | 11 341 |
000000 000440 000547 000100 000110 000330 004040 004445 004100 001040 001010 001740 003000 003010 003030 007040 007030 007104 007110 040000 040070 047100 050007 017000 070000 070077 071010 400101 400313 401033 407103 411033 431033 500033 503330 100045 100011 100414 101044 101301 103011 107131 140414 141044 111044 133011 177711 304011 305011 305141 307141 344011 345011 354010 314001 377711 700000 700337 707100 707141 707110 717000 730007 770070 770711 |
| Langton's loop (86 细胞, 8 状态) | 22222222 2170140142 2022222202 272 212 212 212 202 212 272 212 21222222122222 207107107111112 2222222222222 |
000000 000012 000020 000030 000050 000063 000071 000112 000122 000132 000212 000220 000230 000262 000272 000320 000525 000622 000722 001022 001120 002020 002030 002050 002125 002220 002322 005222 012321 012421 012525 012621 012721 012751 014221 014321 014421 014721 016251 017221 017255 017521 017621 017721 025271 100011 100061 100077 100111 100121 100211 100244 100277 100511 101011 101111 101244 101277 102026 102121 102211 102244 102263 102277 102327 102424 102626 102644 102677 102710 102727 105427 111121 111221 111244 111251 111261 111277 111522 112121 112221 112244 112251 112277 112321 112424 112621 112727 113221 122244 122277 122434 122547 123244 123277 124255 124267 125275 200012 200022 200042 200071 200122 200152 200212 200222 200232 200242 200250 200262 200272 200326 200423 200517 200522 200575 200722 201022 201122 201222 201422 201722 202022 202032 202052 202073 202122 202152 202212 202222 202272 202321 202422 202452 202520 202552 202622 202722 203122 203216 203226 203422 204222 205122 205212 205222 205521 205725 206222 206722 207122 207222 207422 207722 211222 211261 212222 212242 212262 212272 214222 215222 216222 217222 222272 222442 222462 222762 222772 300013 300022 300041 300076 300123 300421 300622 301021 301220 302511 401120 401220 401250 402120 402221 402326 402520 403221 500022 500215 500225 500232 500272 500520 502022 502122 502152 502220 502244 502722 512122 512220 512422 512722 600011 600021 602120 612125 612131 612225 700077 701120 701220 701250 702120 702221 702251 702321 702525 702720 |
| Sayama's SDSR loop(86 细胞, 9 状态) | 222222222222222 27017017017011112 21222222222222212 202 212 272 212 212 212 202 212 272 212 212 212 202 212 272 272 212 202 202 212 272 272 21222222222222202 20710710710410412 222222222222225 |
000012 000043 000122 000152 000212 000242 000422 000452 000752 001022 002141 002171 002322 011221 012121 012321 012421 012451 012526 012626 012721 012751 013421 013721 014221 014251 014321 014351 014421 014621 017221 017251 017561 017621 017721 100011 100121 100211 100244 100277 101211 101244 101277 102021 102111 102121 102131 102211 102244 102277 102324 102414 102424 102434 102511 102527 102543 102577 102717 102727 102735 105121 105424 105727 106211 106244 106277 111121 111221 111244 111251 111277 111621 112121 112131 112151 112221 112244 112277 112321 112424 112434 112527 112543 112577 112626 112727 112735 113221 113321 115424 115727 116244 116277 122244 122277 122434 122737 123244 123277 124266 124333 126276 200012 200022 200042 200052 200060 200071 200122 200152 200212 200222 200232 200242 200260 200272 200324 200423 200452 200545 200575 200620 200722 200752 201022 201122 201222 201422 201722 202022 202032 202052 202065 202073 202122 202152 202212 202222 202232 202323 202422 202452 202525 202620 202650 202722 202752 203122 203222 203422 203452 203722 204122 204222 204422 205122 205425 205725 206125 206212 206425 206725 207122 207222 207722 211222 212222 212232 212242 212272 212323 213222 214222 216222 217222 222242 222272 222342 222372 222432 222442 222732 222772 223243 223273 300013 300022 300032 300043 300074 300123 300322 300421 301021 301250 302123 302423 302521 302723 303321 312123 312423 312521 312723 324243 324251 324273 325271 327273 400001 400021 401020 401120 401220 401250 401620 402120 402150 402221 402321 402626 403120 403221 500025 500125 500215 500232 500245 500275 500425 500725 502022 502052 502125 502152 502425 502725 503120 602022 602122 602220 602422 602722 612220 622240 622270 701020 701120 701220 701250 701620 702120 702150 702221 702320 702626 703120 |
| Langton's ant (2个状态) | 从任意一点往一个方向（上、下、左、右选其一）出发蚂蚁进行游走，它的规则有两条： 1、如果走到的格子为空，则占领这个格子并且蚂蚁顺时针旋转90度；2、如果走 到的格子已经被占领，则把这个格子的状态变为空，并且逆时针旋转90度。 |
相关的参考文献
1、C.G.Langton. Self-reproduction in cellular automata. Physica D, Vol. 10, pages 135-144, 1984.
2、C.G.Langton. Studying artificial life with cellular automata Physica D,Vol.22,pages 120-149,1986
3、J. Byl. Self-Reproduction in small cellular automata. Physica D, Vol. 34, pages 295-299, 1989.