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 条
  • [31] A Cellular Automata based Classification Algorithm
    Usta, Tugba
    Dundar, Enes Burak
    Korkmaz, Emin Erkan
    ICPRAM: PROCEEDINGS OF THE 8TH INTERNATIONAL CONFERENCE ON PATTERN RECOGNITION APPLICATIONS AND METHODS, 2019, : 155 - 162
  • [32] Cellular automata evolution for pattern classification
    Maji, P
    Sikdar, BK
    Chaudhuri, PP
    CELLULAR AUTOMATA, PROCEEDINGS, 2004, 3305 : 660 - 669
  • [33] A Generalization of Automorphism Classification of Cellular Automata
    Nishio, Hidenosuke
    JOURNAL OF CELLULAR AUTOMATA, 2012, 7 (02) : 167 - 177
  • [34] Cellular Automata Learning Algorithm for Classification
    Wongthanavasu, Sartra
    Ponkaew, Jesada
    2014 INTERNATIONAL ELECTRICAL ENGINEERING CONGRESS (IEECON), 2014,
  • [35] A Note on Elementary Cellular Automata Classification
    Martinez, Genaro J.
    JOURNAL OF CELLULAR AUTOMATA, 2013, 8 (3-4) : 233 - 259
  • [36] THE CLASSIFICATION OF HOMOGENEOUS AND SYMMETRICAL CELLULAR AUTOMATA
    MAKOWIEC, D
    ACTA PHYSICA POLONICA B, 1992, 23 (04): : 299 - 311
  • [37] CLASSIFICATION OF SQUARE LATTICE CELLULAR AUTOMATA
    STAUFFER, D
    PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 1989, 157 (02) : 645 - 655
  • [38] A HIERARCHICAL-CLASSIFICATION OF CELLULAR AUTOMATA
    GUTOWITZ, HA
    PHYSICA D, 1990, 45 (1-3): : 136 - 156
  • [39] CLASSIFICATION OF TRIANGULAR AND HONEYCOMB CELLULAR AUTOMATA
    GERLING, RW
    PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 1990, 162 (02) : 196 - 209
  • [40] Kolmogorov complexity and cellular automata classification
    Dubacq, JC
    Durand, B
    Formenti, E
    THEORETICAL COMPUTER SCIENCE, 2001, 259 (1-2) : 271 - 285
12345