Life Worth Mentioning: Complexity in Life-Like Cellular Automata
Life Worth Mentioning: Complexity in Life-Like Cellular Automata
复制标题
值得一提的生活：栩栩如生的元胞自动机的复杂性
DOI：
10.1162/artl_a_00348
复制
发表时间：
2021
期刊：
影响因子：
2.6
通讯作者：
Hiroki Sayama
中科院分区：
文献类型：
--
作者：
Eric Peña;Hiroki Sayama
摘要细胞自动机(CA)因能够从简单的局部规则生成复杂的全局模式而备受赞誉。已故英国数学家约翰·霍顿·康韦在1970年提出了他杰出的生命游戏(Life)CA，自那以来一直是最典型的CA结构之一-能够产生无数复杂的动态模式和计算普适性。生命和其他几个类似生命的规则被归类为一组具有美学和动态趣味性的CA规则，其特点是行为复杂。然而，类似分类的类生命规则之间的严格量化比较尚未完全建立。在这里，我们展示了生活能够保持与类似规则一样的复杂性，同时保持最节俭。换句话说，生命在整个演化过程中包含了一致的复杂性，与其他类似生命的规则相比，规则条件的数量最少。我们还发现，高密度类生命规则的复杂性本身包含生命规则作为子集，形成了明显的凹密度-复杂性关系，从而提出了最优复杂性候选。我们的结果还支持这样的概念，即Life作为培养结构和随机性之间的平衡的基本成分，以保持低密度和高密度制度的2D CA的复杂性，特别是在多次迭代中。这部作品突出了约翰·霍顿·康威的天才，证明了他永恒的奇迹，也就是简单地说：生命。
Abstract Cellular automata (CA) have been lauded for their ability to generate complex global patterns from simple local rules. The late English mathematician, John Horton Conway, developed his illustrious Game of Life (Life) CA in 1970, which has since remained one of the most quintessential CA constructions—capable of producing a myriad of complex dynamic patterns and computational universality. Life and several other Life-like rules have been classified in the same group of aesthetically and dynamically interesting CA rules characterized by their complex behaviors. However, a rigorous quantitative comparison among similarly classified Life-like rules has not yet been fully established. Here we show that Life is capable of maintaining as much complexity as similar rules while remaining the most parsimonious. In other words, Life contains a consistent amount of complexity throughout its evolution, with the least number of rule conditions compared to other Life-like rules. We also found that the complexity of higher density Life-like rules, which themselves contain the Life rule as a subset, form a distinct concave density-complexity relationship whereby an optimal complexity candidate is proposed. Our results also support the notion that Life functions as the basic ingredient for cultivating the balance between structure and randomness to maintain complexity in 2D CA for low- and high-density regimes, especially over many iterations. This work highlights the genius of John Horton Conway and serves as a testament to his timeless marvel, which is referred to simply as: Life.