主题
Search

生命游戏


生命游戏是最著名的二维细胞自动机,由约翰·H·康威发明,并在马丁·加德纳于 1970 年 10 月开始的《科学美国人》专栏中普及。生命游戏最初是通过手工使用计数器进行(即,产生连续世代),但在计算机上的实现大大提高了探索模式的便利性。

生命细胞自动机的运行方式是在二维网格上放置一些填充的单元格。然后,每一代都会根据周围单元格的状态打开或关闭单元格。规则定义如下。检查当前单元格周围的所有八个单元格,看它们是否处于打开状态。任何处于打开状态的单元格都会被计数,然后使用此计数来确定当前单元格会发生什么。

1. 死亡:如果计数小于 2 或大于 3,则当前单元格关闭。

2. 生存:如果 (a) 计数正好为 2,或者 (b) 计数正好为 3 且当前单元格处于打开状态,则当前单元格保持不变。

3. 诞生:如果当前单元格处于关闭状态且计数正好为 3,则当前单元格打开。

生命游戏是一种全域细胞自动机,可以使用内置命令按如下方式实现CellularAutomaton,其中初始条件被指定为一个二进制矩阵 m,并返回世代 g_1g_2 的结果。(这里,g=0 对应于初始模式。)

  Life[m_List?MatrixQ, {g1_Integer, g2_Integer}] :=
    CellularAutomaton[
      {
        224,
        {2, {{2, 2, 2}, {2, 1, 2}, {2, 2, 2}}},
        {1, 1}
      },
      {m, 0},
      g2,
      {
        {g1, g2},
        Automatic
      }] /; g2>=g1
StillLifes

从一代到下一代不发生变化的模式被称为静止生命,并被称为具有周期 1。上面说明了几个静止生命。对于 n 个单元格,n=1, 2, 3, ... 的静止生命的数量为 0, 0, 0, 2, 1, 5, 4, 9, 10, 25, 46, 121, 240, 619, 1353, ... (OEIS A019473)。

在一组配置中循环的模式称为振荡器。

Puffer train

康威最初认为,没有任何模式可以产生无限数量的单元格,并向任何能在 1970 年底之前找到反例的人提供了 50 美元的奖金(Gardner 1983,第 216 页)。随后发现了许多反例,包括枪和喷射列车(如上图所示)。

GardensofEden

没有父模式的生命模式被称为伊甸园(原因显而易见)。第一个这样的模式直到 1971 年才被发现,现在已知许多(LifeWiki)。

306-cell unique father pattern

长期悬而未决的“唯一父问题”,即确定是否存在一种模式,该模式具有父模式但没有祖父模式(Wainwright 1972,Gardner 1983,第 249 页),由 Ilkka Törmä 和 Ville Salo 于 2022 年 1 月解决,他们发现了一个 374 个单元格的此类模式示例,这一结果很快被简化为上面说明的 306 个单元格的模式(apgoucher 2022,LifeWiki)。

令人惊讶的是,生命是一种通用细胞自动机,从某种意义上说,它实际上能够模拟任何细胞自动机图灵机或任何其他可以转换为已知为通用的系统的系统。Berlekamp 等人 (1982) 和 Gosper (Gardner 1983, pp. 250-253) 独立给出了生命通用性的证明概要。2000 年左右,P. Rendell (Rendell, Adamatzky 2001) 在生命中显式实现了一个可以扩展为通用图灵机的图灵机。虽然 Rendell 的机器可以通过简单地将其磁带无限化而制成“真正的”通用计算机,但他既没有注意到这一事实,也没有提供通用图灵机的实际构造。随后,在 2002 年 11 月 11 日,P. Chapman 基于 D. Hickerson 的“滑动块内存”方法构建了一种生命模式,该模式实现了通用寄存器机的操作。与 Rendell 图灵机的有限磁带不同,Chapman 机器的寄存器中的值是无界的,这使其成为生命游戏中通用计算的真实模型。Chapman 的构造在 4558×21469 的区域中使用 268096 个活动单元格,并且在 400 MHz 计算机上每秒可以计算大约 20 代。

更令人惊讶的是,正如 Wolfram (2002) 所表明的那样,即使是一维细胞自动机(特别是规则 110)也可以是通用的。

已经构建了类似于生命但具有不同规则的二维细胞自动机游戏,并命名为 HexLife 和 HighLife。HashLife 是一种生命算法,它通过将子模式存储在哈希表中并使用它们向前跳过,有时一次跳过数千代,从而实现显着的速度。


另请参阅

细胞自动机, Larger than Life, 规则 110, 全域细胞自动机, 通用细胞自动机, 通用性

使用 Wolfram|Alpha 探索

参考文献

Adamatzky, A. (Ed.). Collision Based Computing. Mult.-Valued Log. 6, pp. 397-514, 2001. Yverdon: Gordon and Breach, 2001.apgoucher. "29-Year-Old Conway Conjecture Settled." Jan. 14, 2022. https://cp4space.hatsya.com.Bays, C. "A Note on the Game of Life in Hexagonal and Pentagonal Tessellations." Complex Systems 15, 245-252, 2005.Berlekamp, E. R.; Conway, J. H.; and Guy, R. K. "What Is Life?" Ch. 25 in Winning Ways for Your Mathematical Plays, Vol. 2: Games in Particular. London: Academic Press, 1982.Callahan, P. "Patterns, Programs, and Links for Conway's Game of Life." http://www.radicaleye.com/lifepage/.Chapman, P. "Life Universal Computer." http://www.igblan.com/ca/.Flammenkamp, A. "Game of Life." http://www.uni-bielefeld.de/~achim/gol.html."The Game of Life." Math Horizons. p. 9, Spring 1994.Gardner, M. "The Game of Life, Parts I-III." Chs. 20-22 in Wheels, Life, and other Mathematical Amusements. New York: W. H. Freeman, 1983.Hensel, A. "PC Life Distribution." http://www.mindspring.com/~alanh/lifep.zip.Hensel, A. "Conway's Game of Life." Includes a Java applet for the Game of Life. http://www.ibiblio.org/lifepatterns/.Koenig, H. "Game of Life Information." http://pentadecathlon.com/lifeInfo.php.LikeWiki. "Garden of Eden." https://conwaylife.com/wiki/Garden_of_Eden.LifeWiki. "Unique Father Pattern." https://conwaylife.com/wiki/Unique_father_problem.Update a linkMcIntosh, H. V. "Life." http://www.cs.cinvestav.mx/mcintosh/oldweb/life.htmlPoundstone, W. The Recursive Universe: Cosmic Complexity and the Limits of Scientific Knowledge. New York: Morrow, 1985.Rendell, P. "This Is a Turing Machine Implemented in Conway's Game of Life." http://www.rendell.uk.co/gol/tm.htm.Resnick, M. and Silverman, B. "A Zoo of Life Forms." http://lcs.www.media.mit.edu/groups/el/projects/emergence/life-zoo.html.Sloane, N. J. A. Sequence A019473 in "The On-Line Encyclopedia of Integer Sequences."Toffoli, T. and Margolus, N. Cellular Automata Machines: A New Environment for Modeling. Cambridge, MA: MIT Press, 1987.Wainwright, R. T. "LifeLine." http://members.aol.com/life1ine/life/lifepage.htm.Wainwright, R. T. LifeLine: A Quarterly Newsletter for Enthusiasts of John Conway's Game of Life. Nos. 1-11, 1971-1973.Wainwright, R. T. "The Unique Grandfather Problem." Lifeline 6, p. 1, Oct. 1972.Weisstein, E. W. "Eric Weisstein's Encyclopedia of the Game of Life." http://www.ericweisstein.com/encyclopedias/life/.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, 2002.

在 Wolfram|Alpha 上引用

生命游戏

请引用为

韦斯坦因,埃里克·W. “生命游戏”。来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/GameofLife.html

主题分类