A4 Refereed article in a conference publication

Topology Inspired Problems for Cellular Automata, and a Counterexample in Topology




AuthorsVille Salo, Ilkka Törmä

EditorsEnrico Formenti

Publication year2012

JournalElectronic Proceedings in Theoretical Computer Science

Book title Proceedings 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journées Automates Cellulaires

Article number5

Series titleElectronic Proceedings in Theoretical Computer Science

Volume9

First page 53

Last page68

Number of pages16

ISSN2075-2180

DOIhttps://doi.org/10.4204/EPTCS.90.5(external)


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.

Downloadable publication

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.





Last updated on 2024-26-11 at 22:34