An Experimental Study of Noise and Asynchrony in Elementary Cellular Automata with Sampling Compensation

An Experimental Study of Noise and Asynchrony in Elementary Cellular Automata with Sampling Compensation by Fernando Silva, and Luís Correia

 Abstract: This article focuses on the set of 32 legal Elementary Cellular Automata. We perform an exhaustive study of the systems' response under: (i) $\alpha$-asynchronous dynamics, from full asynchronism to perfect synchrony, (ii) $\kappa$ asynchrony, which extends $\alpha$-asynchrony to compensate for less cell activity, and (iii) $\phi$ noise scheme, a perturbation that affects the local transition function and causes a cell to probabilistically miscalculate the new state when it is updated. We propose a new classification in three classes under asynchronous conditions: $\alpha$ invariant, $\alpha$-robust, and $\alpha$-dependent. We classify the 32 legal ECA according to the degree of behavioural modification, and we show that our classifying scheme provides results coherent with the density-based classification. We also show that $\kappa$-asynchrony provides results comparable to synchronous systems, both quantitatively and qualitatively. Subsequently, we analyse the effects of including different levels of noise in synchronous systems. We identify different responses to noise, including systems that are robust to asynchrony and susceptible to noise. To conclude, we investigate the behavioural changes caused by simultaneous asynchrony and noise in models tolerant to both perturbations. We describe a number of effects caused by the interplay of noise and asynchrony, thus further reinforcing that both aspects are pertinent for future studies.

Description of the dataset: 

The dataset contains a number of results and data with respect to our experimental study of noise and asynchrony in Elementary Cellular Automata. The dataset is divided into three folders, namely:

1 - folder "Asynchrony", in which we provide a number of results related to the classification of the 32 ECA in three classes, $\alpha$-invariant, $\alpha$-robust, and $\alpha$-dependent, according to the degree of behavioural modification under asynchronous conditions. We also analyse and compare the effects of $\kappa$-asynchrony and $\alpha$-asynchrony in CA evolution.

2 - folder "Noise" 

Stochastic noise in the local transition function consists of a perturbation to a cell's state when it is updated. We examined the impact of noise in the 32 legal rules. CA are subject to noise and updated according to a synchronous scheme in order to distinguish the effects of noise and the effects of asynchronous updating. Analysis is conducted with respect to the different classes of response to $\alpha$-asynchrony. We define 4 levels of tolerance to noise, coherent with our proposed classification according to the degree of behavioural modification under asynchronous conditions. The four degrees for classifying systems subject to noise are: (i) $\phi$ invariant as models that instantaneously forget perturbations due to noise, (ii) $\phi$-MR when the asymptotic inter-CA correlation >= 0.5, (iii) $\phi$ LR as models where perturbations are contained in the neighbourhood but the asymptotic inter-CA correlation < 0.5, and (iv) $\phi$-dependent as models highly susceptible to noise in which a single perturbation causes significant changes in behaviour.

3 - Folder "Noise and Asynchrony"

We analyse the degree of behavioural modification when systems are simultaneously subject to asynchrony and noise. We investigate how models robust or invariant to asynchrony and noise, separately, respond when both aspects are present. We concentrate our study in two sets of CA: (i) $\alpha$-invariant and $\phi$-invariant, i.e., ECA 0, 32, 128, 160, 250, and 254, and (ii) $\alpha$ invariant and $\phi$-MR, namely ECA 4, 36, 72, 104, 164, and 218. Remaining systems part of the 32 legal rules are sensitive to the presence of noise and/or asynchrony. Expectedly, these systems exhibit low robustness to simultaneous perturbations. We represented the asymptotic inter-CA correlation between $\alpha$-asynchronous and synchronous systems, both of which are subject to noise. The set of values for different synchrony rates and noise rates is represented in a three dimensional space, which is projected on a two dimensional sampling surface.