Life worth mentioning: Complexity in life-like cellular automata

Eric Peña*, Hiroki Sayama


研究成果: Article査読

1 被引用数 (Scopus)


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.

ジャーナルArtificial Life
出版ステータスPublished - 2021 11月 2

ASJC Scopus subject areas

  • 生化学、遺伝学、分子生物学(全般)
  • 人工知能


「Life worth mentioning: Complexity in life-like cellular automata」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。