康威生命游戏

生命游戏是英国数学家约翰·何顿·康威在1970年发明的细胞自动机，并被证明了图灵完备性。它最初于1970年10月在《科学美国人》杂志中马丁·葛登能的“数学游戏”专栏出现。其原理十分简单，即在一个二维平面上生存着若干个细胞，其在下一时刻存活与否取决于周围8个格子内细胞存在情况，具体规则如下：如果周围8格内有2个细胞，则此格保持原状态。如果周围8格内有3个细胞，则此格出现细胞（或保持有细胞状态）如果周围8格内细胞数量小于等于1或者大于等于4，则此格细胞因为孤独或过于拥挤而变为空格（或保持空格状态）1、历史概述最早的发现是在1969年末，康威和研究生初步探索B3/S23时，发现的R-pentomino五格多米诺，以及随之产生的Glider滑翔机。70年代主要是以常见的太空船、振荡体为主。 其中包括了queen bee shuttle蜂巢，及由其为蓝本建造的高斯帕滑翔机枪（Gosper glider gun）。当然还有速度为2/c的大、中、小型飞船。80年代，高一些周期的振荡体被发现，比如Achim的p4物体Mold和Jam。还有c/3、c/4的太空船。1991年是一个新起点，这要归功于David Bell写的"lifesrc"搜索程序，2c/5和c/12这样的新速度也有了对应的太空船。90年代，也是搜索程序大繁荣的时代，具体可以查看David Eppstein的论文《Searching for Spaceships》2、领域分类。（1）纯理论研究。比如康威老爷子的两个证明，一是证明了B3/S23规则图灵完备，二证明了生命游戏世界里存在“可以自我复制”的物体。还有对特定细胞数能存在多少still life静止体的研究（A019473序列）。（2）自然图形搜寻。对新的静止体、振荡体、太空船等图形的搜索。目前主要聚焦于，未发现的新周期，和没有太空船存在的新速度。比如，从周期2到周期60，几乎所有的周期都有振荡体存在，唯独缺少一个周期19（p19）。还有太空船的新速度，4c/9等速度还没有发现相应的太空船。（3）大型图案建造。主要是指应用已发现的自然物体，和理论研究发现的自然规律，人工改造建造各种各类的有趣图案。比如各种枪、播种机、滑翔机合成。比如质数机，可以产生相应的滑翔机质数序列。最为复杂的工程之一，当属Meixel元像素，它可以在生命世界中构造一组网格，来运行生命世界。