自我复制的元胞自动机

来自集智百科
跳转到: 导航搜索

蚁迹寻踪

目录

程序简介

  • 名 称: 能自我繁殖功能的细胞自动机
  • 作 者: 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.

个人工具
名字空间
操作
导航
工具箱