任意相鄰元胞自動機(jī)中的復(fù)制斑圖

1、448吉林大學(xué)學(xué)報(bào)(理學(xué)版)第43卷研究簡報(bào)任意相鄰元胞自動機(jī)中的復(fù)制斑圖閆滿，李萬龍閆廣武（長春工業(yè)大學(xué) 計(jì)算機(jī)科 學(xué)與工程學(xué)院，長春130012）（吉林大學(xué) 數(shù)學(xué)學(xué)院，長春130012）摘要：給出了任意相鄰元胞自動機(jī)復(fù)制的動力學(xué)描述,發(fā)現(xiàn)一種新的復(fù)制現(xiàn)象：拷貝復(fù)制.通過研究Boo lean型變量和概率型變量的演化方程，發(fā)現(xiàn)這種復(fù)制行為只發(fā)生在Boolean型變量中，概率型的演化結(jié)果不具有復(fù)制行為.即使在Boo lean型變量中，相鄰點(diǎn)的作用與遠(yuǎn)程點(diǎn)的作用也存在著差別.關(guān)鍵詞：元胞自動機(jī)；復(fù)制；任意相鄰中圖分類號:N94 文獻(xiàn)標(biāo)識碼：A文章編號：1671 5489（2005） 04 0447

2、 03Reproduction Patterns in the Arbitrary NeighborhoodRule Cellular Autom ataYAN M an LIW an long(School of ComputerScienceand Engineering，Changchun University of Technology, Changchun 130012 China)YAN Guangwu(College ofM athematics Jilin Universit/， Changchun 130012 China)Abstrac： t W e proposed a

3、new dynam icaldescription for the arbitrary neghborhood ru le cellular auton ata and a new kind of reproduct ion pattern copy reproducti on. By com pari ng the Boo lea n equati onw ith the probabili ty ones it can be found that th is reproduct ion only appears in the Boolea n equati on， the rule of

4、the probab ility equation doesn t shov th s reproduction， even there is d ifference between the near neighborhood rule and far neghborhood n the Boolean equationKey words： cellular automata reproduction arb itrary neighborhood元胞自動機(jī)是一種整體性質(zhì)完全依賴于局部規(guī)則的簡單動力系統(tǒng).研究表明，簡單的元胞自動機(jī)可以涌現(xiàn)出大量的復(fù)雜現(xiàn)象.一個(gè)二維二狀態(tài)的元胞自動機(jī)在每個(gè)二維格

5、點(diǎn)上具有相同的演化規(guī)則，1 2根據(jù)演化規(guī)則，決定其下一步的狀態(tài) ，.自我復(fù)制元胞自動機(jī)是一類特殊的元胞自動機(jī)，最初是由VonNeumann 1提出來用于研究類似生物這樣自我復(fù)制過程的.他證明了存在這樣的元胞自動機(jī)，但是這個(gè)元胞自動機(jī)相當(dāng)復(fù)雜，甚至無法給出具體的演化規(guī)則.后來，Codd3簡化了 Von Neumann的自我復(fù)制元胞自動機(jī)，將原來的29個(gè)狀態(tài)縮減到8個(gè)，即使這樣，仍然很復(fù)雜，也無法給出具體的演化規(guī)則和計(jì)算機(jī)再現(xiàn).Langton4給出了實(shí)現(xiàn)自我復(fù)制規(guī)則的優(yōu)化標(biāo)準(zhǔn)和必要條件，之后人們給出了更簡單的自我復(fù)制元胞自動機(jī)57.這些元胞自動機(jī)的復(fù)制都是針對具體的構(gòu)型，而不是任意構(gòu)型.1971年

6、，F(xiàn)redkin給出了一種可以實(shí)現(xiàn)任意構(gòu)型復(fù)制的元胞自動機(jī)811. Fredk in元胞自動機(jī)中的規(guī)則稱為Fredk in規(guī)則，這樣的規(guī)則可以進(jìn)行強(qiáng)化，例如，文獻(xiàn)12給出了 3規(guī)則和三維Fredkin規(guī)則，同樣可收稿日期：2004 12 29作者簡介：閆 滿（1979-），女，漢族，碩士研究生，從事軟件工 程與復(fù)雜系 統(tǒng)的研究，E mail yanman99 sohu. com.聯(lián)系人： 閆廣武（1964-），男，漢族，博士，教授，博士生導(dǎo)師，從事復(fù)雜系統(tǒng)與流體力學(xué)的研究，E m ai： yangwamail cn.基金項(xiàng)目：國家自然科學(xué)基金（批準(zhǔn)號：60274064 ）和吉林

7、大學(xué)創(chuàng)新基金（批準(zhǔn)號：2004CX041）.1994-2011 China Academie Journal I .kctronic PublishingAll rigpte reserved,Tff以給出任意初始構(gòu)型的復(fù)制本文在此基礎(chǔ)上，進(jìn)一步探討任意相鄰1規(guī)則的動力學(xué)行為結(jié)果表明，相鄰 1規(guī)則元胞自動機(jī)的演化結(jié)果是新型的復(fù)制，即拷貝復(fù)制、擴(kuò)散復(fù)制和遠(yuǎn)距離復(fù)制1任意相鄰的二維元胞自動機(jī)考慮一個(gè)二維二狀態(tài)元胞自動機(jī)用S j表示時(shí)刻n位置(i j)的狀態(tài)，S；j= 1表示存在粒子S，j = 0表示不存在粒子.定義1 n+ 1時(shí)刻位置(i j)的狀態(tài)S；+j1僅與Sn，和§，?有關(guān)，其中

8、(，)和(！，？)為任意網(wǎng)格點(diǎn) 稱這樣的相鄰為任意二相鄰.定義1中，可以取以下幾種特殊,情況(1)(，)=(，j)，(!，?) =(i-1,j- 1)；(2)(，)=(，j)，(!，?) =(i-1,j)；(3)(，)=(i+ 1, j+ 1)，(!, ?)=(i- 1 j- 1)；(4)(，)=(，j)，(!，?) =(i-5j).定義2相鄰1規(guī)則：n+ 1nnnnSi，j = S，(1 - S!，?) + S!，? ( 1- S，).( 1)nnn用f i j表示Si j的系綜平均，則f i j實(shí)際上是概率分布密度.對定義2中的演化規(guī)則做系綜平均，可得n+1nnnnf i，j = f，(1

9、- f !，?) + f !，?(1 - f，).(2)式(1)具有很好的復(fù)制性質(zhì)，而概率型的式(2)沒有復(fù)制性質(zhì).2二維元胞自動機(jī)的復(fù)制2選擇區(qū)間Q 1 0, 1上的圓環(huán)：0 001! R ! 0 004作為初始構(gòu)型，如圖1所示.下面分別給出 不同相鄰的復(fù)制情況：(1) (, ) = (i j), (!,?) =不變，在正方形的對角線上出現(xiàn)拷貝(i- 1, j- 1).此時(shí)的復(fù)制為拷貝型復(fù)制 ,如圖2所示.即演化的結(jié)果是初始圓環(huán)448吉林大學(xué)學(xué)報(bào)(理學(xué)版)第43卷448吉林大學(xué)學(xué)報(bào)(理學(xué)版)第43卷Fift. I Initial ring(2) ( , ) = (, j), (!,?) =F

10、ig. 4 PolTit-fiynimertry-reproductwnFig* 3 Horizantal-selF-repnMiuctiofiFig, 2 Sdf-reproduction(i- 1 j).這種情況與(1)相同，也是拷貝復(fù)制，僅位置不同，如圖3所示.(3) ( , ) = (i+ 1, j+ 1), (!,?)=( i- 1, j- 1).這種相鄰由于是對稱的，因此，出現(xiàn)的復(fù)制為 擴(kuò)散型復(fù)制，即初始圓環(huán)不再保留，出現(xiàn)對稱的兩個(gè)圓環(huán).如圖4所示.448吉林大學(xué)學(xué)報(bào)(理學(xué)版)第43卷由于遠(yuǎn)距離的作用，將出現(xiàn)干擾(4) ( ,) = (, j),(!,?)=( i- 5 j).這是

11、一種遠(yuǎn)距離相鄰條紋.這種條紋連同原初始圓環(huán)一同被復(fù)制，如圖5所示.上述復(fù)制中，拷貝復(fù)制、:門擴(kuò)散復(fù)制和遠(yuǎn)距離復(fù)制是新的復(fù)制現(xiàn)象 如然而，當(dāng)狀態(tài)變量取Qv1上的第4期閆 滿，等：任意相鄰元胞自動機(jī)中的復(fù)制斑圖449實(shí)數(shù)時(shí)，任何復(fù)制現(xiàn)象都將會消失此時(shí)的動力學(xué)方程為方程 (2),是離散形式的擴(kuò)散方程，其計(jì)算結(jié) 果具有擴(kuò)散性質(zhì)圖6為方程(2)在第32步的演化結(jié)果.其中,(,)=(,j),(!,?) =(i- 1 j- 1).圖6(A)為顯示大于0.5的值，圖 的演化結(jié)果不具有復(fù)制行為.6( B)為顯示大于Q 45的值.圖6結(jié)果表明，方程(2)Fig. 5 Far-distaiue-reproducti

12、on綜上可見，本文通過選擇任意相鄰的演化規(guī)則Fig, 6 Evolution results of equation (2得到幾個(gè)新"的復(fù)制現(xiàn)象：(1) 拷貝復(fù)制.這種復(fù)制是在不變的模本下對原構(gòu)型的拷貝(2) 擴(kuò)散復(fù)制.原模本消失了，出現(xiàn)的復(fù)制具有擴(kuò)散現(xiàn)象(3) 遠(yuǎn)距離復(fù)制.這種復(fù)制連同干涉條紋也一同復(fù)制.上述3種現(xiàn)象在概率型元胞自動機(jī)中不會出現(xiàn).參考文獻(xiàn)1 Von Neumann J The Theory Self reproducing A utomata M . Burks A W, ed Urbana University I llinois Press 19662 Wolf

13、rams A New K ind of Science M . Illinois Wolfram Media Inc, 20023 Codd E F. Cellu lar AutomataM . NewYork Academic Press 19684 Langt)nCG. Self reproduction in C ellular Au tDmata J. Phy sicaD, 1984 10 135? 1445 ReggaJA, A m entrout S L, Chou H H, et al. Smple Systens that Exhibit Self d rectedR epli

14、cationJ. Science1993 259 1282? 12876 BylJ Self reproduction n Small Ce llular A utomata J. PhysicaD, 1989 34 295? 2997 PerrierJY, SipperM, Zahnd J Toward a V iable Self reproducticing U n iversal Com puter J.PhysicaD, 199697335? 3528 Chopard B, D rozM. Cellu lar A utomata M odeling of Physical Systm

15、s M . London Cam bridge U n iversity Press 19989 G ianluca Tempost. A New Self reproducing Cellu hr Automata Capable of Construction M . Grenada Span: A dvances n A rtifi c ial L if 199510 Fredkin E. Infomation ProcesGg andT ranm ission n Cellular A utomata R. Massachusetts M IT Press 197111 Fredkin E. D g italM echanics A n Informational ProcessBasedon ReversibleU n versal CA J. PhysicaD, 1990 45 254? 25612 JN Yu liang YAN Guangwu Threedmensional Fredkin rule Cellular