Topological Conjugacy Classification of Cellular Automata

被引：1
|
作者：
Guan, Junbiao [1 ]
Shen, Shaowei [2 ]
机构：
[1] Hangzhou Dianzi Univ, Sch Sci, Hangzhou 310018, Zhejiang, Peoples R China
[2] Zhejiang Gongshang Univ, Coll Stat & Math, Hangzhou 310018, Zhejiang, Peoples R China
来源：
2009 INTERNATIONAL WORKSHOP ON CHAOS-FRACTALS THEORIES AND APPLICATIONS (IWCFTA 2009) | 2009年
关键词：
Cellular automata; global equivalence class; Game of Life; dual rule; symbolic dynamics; topological conjugacy; COMPLEXITY; WOLFRAMS; SCIENCE; KIND;
D O I：
10.1109/IWCFTA.2009.51
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We present a theoretically global equivalence classification of cellular automata (CA) on infinite lattices based on the point of view of topological conjugacy. In particular, based on this platform, we further demonstrate that among approximately 1.34 x 10(154) CA rules with nine variables there exists a dual rule of the famous Game of Life, which has been shown to be capable of universal computation, and therefore this rule can also perform universal computation.
引用
收藏
页码：211 / +
页数：2
相关论文
共 50 条
  • [21] Automorphism Classification of Cellular Automata
    Nishio, Hidenosuke
    FUNDAMENTA INFORMATICAE, 2010, 104 (1-2) : 125 - 140
  • [22] Classification of cellular automata and complexity
    Jin, XG
    Kim, TW
    INTERNATIONAL JOURNAL OF MODERN PHYSICS B, 2003, 17 (22-24): : 4232 - 4237
  • [23] REPRESENTATIONS OF GEOMETRICAL AND TOPOLOGICAL QUANTITIES IN CELLULAR AUTOMATA
    SMITH, MA
    PHYSICA D-NONLINEAR PHENOMENA, 1990, 45 (1-3) : 271 - 277
  • [24] Topological Dynamics of Cellular Automata: Dimension Matters
    Sablik, Mathieu
    Theyssier, Guillaume
    THEORY OF COMPUTING SYSTEMS, 2011, 48 (03) : 693 - 714
  • [25] Topological Dynamics of Cellular Automata: Dimension Matters
    Mathieu Sablik
    Guillaume Theyssier
    Theory of Computing Systems, 2011, 48 : 693 - 714
  • [26] Row subshifts and topological entropy of cellular automata
    Di Lena, Pietro
    Margara, Luciano
    JOURNAL OF CELLULAR AUTOMATA, 2007, 2 (02) : 131 - 139
  • [27] THE TOPOLOGICAL-ENTROPY OF CELLULAR AUTOMATA IS UNCOMPUTABLE
    HURD, LP
    KARI, J
    CULIK, K
    ERGODIC THEORY AND DYNAMICAL SYSTEMS, 1992, 12 : 255 - 265
  • [28] TOPOLOGICAL ENTROPY OF PERIODIC COVEN CELLULAR AUTOMATA
    Liu, Weibin
    Ma, Jihua
    ACTA MATHEMATICA SCIENTIA, 2016, 36 (02) : 579 - 592
  • [29] Connecting Elementary Cellular Automata: Topological Properties of In-between Automata
    Kosela, Piotr
    Bylina, Jaroslaw
    JOURNAL OF CELLULAR AUTOMATA, 2024, 17 (5-6) : 425 - 435
  • [30] A solution to the classification problem with cellular automata
    Uzuna, Arif Orhun
    Usta, Tugba
    Dundar, Enes Burak
    Korkmaz, Emin Erkan
    PATTERN RECOGNITION LETTERS, 2018, 116 : 114 - 120
12345