Reversibility of Elementary Cellular Automata Under Fully Asynchronous Update

Biswanath Sethi 1 Nazim Fatès 2 Sukanta Das 3
2 MAIA - Autonomous intelligent machine
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
Abstract : We investigate the dynamics of Elementary Cellular Automata (ECA) under fully asynchronous update with periodic boundary conditions. We tackle the reversibility issue, that is, we want to determine whether, starting from any initial condition, it is possible to go back to this initial condition with random updates. We present analytical tools that allow us to partition the ECA space into three classes: strongly irreversible, irreversible and recurrent.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

https://hal.inria.fr/hal-00906987
Contributor : Nazim Fatès <>
Submitted on : Thursday, November 21, 2013 - 11:46:38 AM
Last modification on : Tuesday, December 18, 2018 - 4:40:21 PM
Long-term archiving on : Saturday, February 22, 2014 - 4:31:04 AM

File

reversibility-ACA.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00906987, version 1

Citation

Biswanath Sethi, Nazim Fatès, Sukanta Das. Reversibility of Elementary Cellular Automata Under Fully Asynchronous Update. 2013. ⟨hal-00906987v1⟩

Share

Metrics

Record views

166

Files downloads

216