A tutorial on elementary cellular automata with fully asynchronous updating

We present a panorama of the convergence properties of the 256 Elementary Cellular Automata under fully asynchronous updating, that is, when only one cell is updated at each time step. We regroup here various results which have been presented in different articles and expose a full analysis of the b...

Full description

Saved in:
Bibliographic Details
Published in:Natural computing 2020-03, Vol.19 (1), p.179-197
Main Author: Fatès Nazim
Format: Article
Language:English
Subjects:
Boundary conditions
Cellular automata
Convergence
Markov chains
Martingales
Properties (attributes)
Scaling laws
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present a panorama of the convergence properties of the 256 Elementary Cellular Automata under fully asynchronous updating, that is, when only one cell is updated at each time step. We regroup here various results which have been presented in different articles and expose a full analysis of the behaviour of finite systems with periodic boundary conditions. Our classification relies on the scaling properties of the average convergence time to a fixed point. We observe that different scaling laws can be found, which fall in one of the following classes: logarithmic, linear, quadratic, exponential and non-converging. The techniques for quantifying this behaviour rely mainly on Markov chain theory and martingales. Most behaviours can be studied analytically but there are still many rules for which obtaining a formal characterisation of their convergence properties is still an open problem.
ISSN:1567-7818
1572-9796
DOI:10.1007/s11047-020-09782-7