License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.AUTOMATA.2021.3
URN: urn:nbn:de:0030-drops-140128
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14012/
Go to the corresponding OASIcs Volume Portal

Taati, Siamak

Reversible Cellular Automata in Presence of Noise Rapidly Forget Everything (Invited Talk)

pdf-format:
OASIcs-AUTOMATA-2021-3.pdf (0.7 MB)

Abstract

We consider reversible and surjective cellular automata perturbed with noise. We show that, in the presence of positive additive noise, the cellular automaton forgets all the information regarding its initial configuration exponentially fast. In particular, the state of a finite collection of cells with diameter n becomes indistinguishable from pure noise after O(log n) time steps. This highlights the seemingly unavoidable need for irreversibility in order to perform scalable reliable computation in the presence of noise.

BibTeX - Entry

@InProceedings{taati:OASIcs.AUTOMATA.2021.3,
  author =	{Taati, Siamak},
  title =	{{Reversible Cellular Automata in Presence of Noise Rapidly Forget Everything}},
  booktitle =	{27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
  pages =	{3:1--3:15},
  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/opus/volltexte/2021/14012},
  URN =		{urn:nbn:de:0030-drops-140128},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.3},
  annote =	{Keywords: Reversible cellular automata, surjective cellular automata, noise, probabilistic cellular automata, ergodicity, entropy, reversible computing, reliable computing, fault tolerance}
}

Keywords: Reversible cellular automata, surjective cellular automata, noise, probabilistic cellular automata, ergodicity, entropy, reversible computing, reliable computing, fault tolerance
Collection: 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)
Issue Date: 2021
Date of publication: 28.06.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI