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 条

[41] Asynchronous Cellular Automata and Pattern Classification
Sethi, Biswanath
Roy, Souvik
Das, Sukanta
COMPLEXITY, 2016, 21 (S1) : 370 - 386
[42] A code classification for semitotalistic cellular automata
Popovici, Adriana
Numerical Analysis and Applied Mathematics, 2007, 936 : 428 - 431
[43] Conjugacy of One-Dimensional One-Sided Cellular Automata is Undecidable
Jalonen, Joonatan
Kari, Jarkko
SOFSEM 2018: THEORY AND PRACTICE OF COMPUTER SCIENCE, 2018, 10706 : 227 - 238
[44] A complete and efficiently computable topological classification of D-dimensional linear cellular automata over Zm
Manzini, G
Margara, L
THEORETICAL COMPUTER SCIENCE, 1999, 221 (1-2) : 157 - 177
[45] Topological chaos of universal elementary cellular automata rule
Jin, Weifeng
Chen, Fangyue
NONLINEAR DYNAMICS, 2011, 63 (1-2) : 217 - 222
[46] Criterion of Infinite Topological Entropy for Multidimensional Cellular Automata
E. L. Lakshtanov
E. S. Langvagen
Problems of Information Transmission, 2004, 40 (2) : 165 - 167
[47] The topological entropy of nth iteration of an additive cellular automata
Akin, H
APPLIED MATHEMATICS AND COMPUTATION, 2006, 174 (02) : 1427 - 1437
[48] Topological chaos of universal elementary cellular automata rule
Weifeng Jin
Fangyue Chen
Nonlinear Dynamics, 2011, 63 : 217 - 222
[49] Topological Design of Structures Using a Cellular Automata Method
Du, Yixian
Chen, De
Xiang, Xiaobo
Tian, Qihua
Zhang, Yi
CMES-COMPUTER MODELING IN ENGINEERING & SCIENCES, 2013, 94 (01): : 53 - 75
[50] Generalized Reversibility of Topological Dynamical Systems and Cellular Automata
Zhang, Kuize
Zhang, Lijun
JOURNAL OF CELLULAR AUTOMATA, 2015, 10 (5-6) : 425 - 434

← 1 2 3 4 5 →