康威生命

生命游戲是英國數(shù)學(xué)家約翰·何頓·康威在1970年發(fā)明的細(xì)胞自動機，并被證明了圖靈完備性。它最初于1970年10月在《科學(xué)美國人》雜志中馬丁·葛登能的“數(shù)學(xué)游戲”專欄出現(xiàn)。其原理十分簡單，即在一個二維平面上生存著若干個細(xì)胞，其在下一時刻存活與否取決于周圍8個格子內(nèi)細(xì)胞存在情況，具體規(guī)則如下：如果周圍8格內(nèi)有2個細(xì)胞，則此格保持原狀態(tài)。如果周圍8格內(nèi)有3個細(xì)胞，則此格出現(xiàn)細(xì)胞（或保持有細(xì)胞狀態(tài)）如果周圍8格內(nèi)細(xì)胞數(shù)量小于等于1或者大于等于4，則此格細(xì)胞因為孤獨或過于擁擠而變?yōu)榭崭瘢ɑ虮３挚崭駹顟B(tài)）1、歷史概述最早的發(fā)現(xiàn)是在1969年末，康威和研究生初步探索B3S23時，發(fā)現(xiàn)的R-pentomino五格多米諾，以及隨之產(chǎn)生的Glider滑翔機。70年代主要是以常見的太空船、振蕩體為主。 其中包括了queen bee shuttle蜂巢，及由其為藍本建造的高斯帕滑翔機槍（Gosper glider gun）。當(dāng)然還有速度為2c的大、中、小型飛船。80年代，高一些周期的振蕩體被發(fā)現(xiàn)，比如Achim的p4物體Mold和Jam。還有c3、c4的太空船。1991年是一個新起點，這要歸功于David Bell寫的&34;lifesrc&34;搜索程序，2c5和c12這樣的新速度也有了對應(yīng)的太空船。90年代，也是搜索程序大繁榮的時代，具體可以查看David Eppstein的論文《Searching for Spaceships》2、領(lǐng)域分類。（1）純理論研究。比如康威老爺子的兩個證明，一是證明了B3S23規(guī)則圖靈完備，二證明了生命游戲世界里存在“可以自我復(fù)制”的物體。還有對特定細(xì)胞數(shù)能存在多少still life靜止體的研究（A019473序列）。（2）自然圖形搜尋。對新的靜止體、振蕩體、太空船等圖形的搜索。目前主要聚焦于，未發(fā)現(xiàn)的新周期，和沒有太空船存在的新速度。比如，從周期2到周期60，幾乎所有的周期都有振蕩體存在，唯獨缺少一個周期19（p19）。還有太空船的新速度，4c9等速度還沒有發(fā)現(xiàn)相應(yīng)的太空船。（3）大型圖案建造。主要是指應(yīng)用已發(fā)現(xiàn)的自然物體，和理論研究發(fā)現(xiàn)的自然規(guī)律，人工改造建造各種各類的有趣圖案。比如各種槍、播種機、滑翔機合成。比如質(zhì)數(shù)機，可以產(chǎn)生相應(yīng)的滑翔機質(zhì)數(shù)序列。最為復(fù)雜的工程之一，當(dāng)屬MetaPixel元像素，它可以在生命世界中構(gòu)造一組網(wǎng)格，來運行生命世界。