DROPS

Document

DOI: 10.4230/OASIcs.AUTOMATA.2021.6

Rice’s Theorem for Generic Limit Sets of Cellular Automata

Authors: Martin Delacourt

Published in: OASIcs, Volume 90, 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)

Abstract

The generic limit set of a cellular automaton is a topologically defined set of configurations that intends to capture the asymptotic behaviours while avoiding atypical ones. It was defined by Milnor then studied by Djenaoui and Guillon first, and by Törmä later. They gave properties of this set related to the dynamics of the cellular automaton, and the maximal complexity of its language. In this paper, we prove that every non trivial property of these generic limit sets of cellular automata is undecidable.

Cite as

Martin Delacourt. Rice’s Theorem for Generic Limit Sets of Cellular Automata. In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{delacourt:OASIcs.AUTOMATA.2021.6,
  author =	{Delacourt, Martin},
  title =	{{Rice’s Theorem for Generic Limit Sets of Cellular Automata}},
  booktitle =	{27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
  pages =	{6:1--6:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-189-4},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{90},
  editor =	{Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.6},
  URN =		{urn:nbn:de:0030-drops-140151},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.6},
  annote =	{Keywords: cellular automata, dynamical systems, generic-limit sets, Rice’s theorem, subshifts}
}

Document

DOI: 10.4230/LIPIcs.STACS.2015.262

Construction of mu-Limit Sets of Two-dimensional Cellular Automata

Authors: Martin Delacourt and Benjamin Hellouin de Ménibus

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract

We prove a characterisation of \mu-limit sets of two-dimensional cellular automata, extending existing results in the one-dimensional case. This sets describe the typical asymptotic behaviour of the cellular automaton, getting rid of exceptional cases, when starting from the uniform measure.

Cite as

Martin Delacourt and Benjamin Hellouin de Ménibus. Construction of mu-Limit Sets of Two-dimensional Cellular Automata. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 262-274, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{delacourt_et_al:LIPIcs.STACS.2015.262,
  author =	{Delacourt, Martin and Hellouin de M\'{e}nibus, Benjamin},
  title =	{{Construction of mu-Limit Sets of Two-dimensional Cellular Automata}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{262--274},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.262},
  URN =		{urn:nbn:de:0030-drops-49197},
  doi =		{10.4230/LIPIcs.STACS.2015.262},
  annote =	{Keywords: cellular automata, dynamical systems, mu-limit sets, subshifts, measures}
}

Search Results

Documents authored by Delacourt, Martin

Rice’s Theorem for Generic Limit Sets of Cellular Automata

Abstract

Cite as

Construction of mu-Limit Sets of Two-dimensional Cellular Automata

Abstract

Cite as

Thanks for your feedback!

Could not send message