Topological Conjugacy Classification of Cellular Automata

摘要

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×10154 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.