On the reversibility of ECAs with fully asynchronous updating: the recurrence point of view

Abstract : The reversibility of classical cellular automata is now a well-studied topic but what is reversibility when the evolution of the system is stochastic? In this context, we study a particular form of reversibility: the possibility of returning infinitely often to the initial condition after a random number of time steps. This corresponds to the recurrence property of the system. We analyse this property for the 256 elementary cellular automata with a finite size and a fully asynchronous updating, that is, we update only one cell, randomly chosen, at each time step. We show that there are 46 recurrent rules which almost surely come back to their initial condition. We analyse the structure of the communication graph of the system and find that the number of the communication classes may have different scaling laws, depending on the active transitions of the rules (those for which the state of the cell is modified when an update occurs).
Type de document :
Pré-publication, Document de travail
To appear in a monography edited by Andrew Adamatzky 2017
Liste complète des métadonnées


https://hal.inria.fr/hal-01571847
Contributeur : Nazim Fatès <>
Soumis le : jeudi 3 août 2017 - 17:06:48
Dernière modification le : vendredi 4 août 2017 - 01:08:37

Fichier

FatesDasSethi-recurrentECA-hal...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01571847, version 1

Collections

Citation

Nazim Fatès, Biswanath Sethi, Sukanta Das. On the reversibility of ECAs with fully asynchronous updating: the recurrence point of view. To appear in a monography edited by Andrew Adamatzky 2017. <hal-01571847>

Partager

Métriques

Consultations de
la notice

185

Téléchargements du document

22