A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Topology Inspired Problems for Cellular Automata, and a Counterexample in Topology
Tekijät: Ville Salo, Ilkka Törmä
Toimittaja: Enrico Formenti
Julkaisuvuosi: 2012
Journal: Electronic Proceedings in Theoretical Computer Science
Kokoomateoksen nimi: Proceedings 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journées Automates Cellulaires
Artikkelin numero: 5
Sarjan nimi: Electronic Proceedings in Theoretical Computer Science
Vuosikerta: 9
Aloitussivu: 53
Lopetussivu: 68
Sivujen määrä: 16
ISSN: 2075-2180
DOI: https://doi.org/10.4204/EPTCS.90.5
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.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
