Topology inspired problems for cellular automata, and a counterexample in topology

MaRDI QIDQ4986304zbMATH OpenFDO

Authors Ville Salo, Ilkka A. Törmä

Publication date 27 April 2021

Full work available at URL https://arxiv.org/abs/1208.2783, http://eptcs.web.cse.unsw.edu.au/paper.cgi?AUTOJAC2012.5

zbMATH Keywords

Besicovitch distancetopologizationfixed alphabetset of all cellular automata

Mathematics Subject Classification ID

Symbolic dynamics (37B10) Dynamical aspects of cellular automata (37B15) Dynamics in general topological spaces (37B02)

Abstract: We consider two relatively natural topologizations of the set of all cellular automata on a fixed alphabet. The first turns out to be rather pathological, in that the countable space becomes neither first-countable nor sequential. Also, reversible automata form a closed set, while surjective ones are dense. The second topology, which is induced by a metric, is studied in more detail. Continuity of composition (under certain restrictions) and inversion, as well as closedness of the set of surjective automata, are proved, and some counterexamples are given. We then generalize this space, in the sense that every shift-invariant measure on the configuration space induces a pseudometric on cellular automata, and study the properties of these spaces. We also characterize the pseudometric spaces using the Besicovitch distance, and show a connection to the first (pathological) space.

Recommendations

• Surjunctivity for cellular automata in Besicovitch spaces
• The Dynamics of Cellular Automata in Shift-Invariant Topologies
• scientific article; zbMATH DE number 1290306
• Some results about the chaotic behavior of cellular automata
• Mathematical Foundations of Computer Science 2003

Cited in

(5)

• Contours, convex sets and cellular automata. IMPA mathematical publications. 23rd Brazilian mathematics colloquium, Rio de Janeiro, Brazil, July 22--27, 2001.
• The Dynamics of Cellular Automata in Shift-Invariant Topologies
• scientific article; zbMATH DE number 1290306 (Why is no real title available?)
• Surjunctivity for cellular automata in Besicovitch spaces
• Cellular automata and substitutions in topological spaces defined via edit distances

This page was built for publication: Topology inspired problems for cellular automata, and a counterexample in topology

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4986304)