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

<strong>An Experimental Study of Noise and Asynchrony in Elementary Cellular Automata with Sampling Compensation </strong>by Fernando Silva, and Luís Correia <strong>Abstract: </strong>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. <strong>Description of the dataset:</strong> 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 &gt;= 0.5, (iii) $\phi$ LR as models where perturbations are contained in the neighbourhood but the asymptotic inter-CA correlation &lt; 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.

**《带采样补偿的初等细胞自动机中噪声与异步性的实验研究》**
作者：费尔南多·席尔瓦（Fernando Silva）、路易斯·科雷亚（Luís Correia）
**摘要：** 本文聚焦于32种合法初等细胞自动机（Elementary Cellular Automata，ECA）的集合。我们对该系统在以下场景下的响应展开了全面研究：(i) α异步动力学，覆盖完全异步至完全同步的全部区间；(ii) κ异步机制，该机制拓展了α异步性以弥补细胞活跃度较低的情况；(iii) φ噪声方案，一种干扰局部转移函数的扰动方式，会使细胞在更新时以概率性误差计算新状态。我们针对异步条件下的系统提出了全新的三分法分类：α不变类、α鲁棒类与α依赖类。我们依据行为修改程度对32种合法ECA进行分类，并证明该分类方案与基于密度的分类结果具有一致性。此外，我们证实κ异步性在定量与定性层面均可获得与同步系统相近的结果。随后，我们分析了在同步系统中引入不同强度噪声的影响，识别出多样的噪声响应模式，包括对异步性具备鲁棒性但易受噪声干扰的系统。最后，我们探究了同时受异步性与噪声双重扰动的模型所产生的行为变化，描述了噪声与异步性相互作用带来的多种效应，进一步凸显了这两个因素在未来研究中的重要价值。
**数据集说明：** 本数据集包含我们针对初等细胞自动机中噪声与异步性开展实验研究所得的各类结果与数据。数据集分为三个文件夹，具体如下：
1. 文件夹「异步性」：其中收录了32种ECA基于异步条件下的行为修改程度划分为α不变类、α鲁棒类与α依赖类的相关结果。我们还分析并对比了κ异步性与α异步性在细胞自动机（Cellular Automata，CA）演化过程中的影响。
2. 文件夹「噪声」：局部转移函数中的随机噪声指细胞在更新时对其状态施加的扰动。我们考察了噪声对32种合法规则的影响。为区分噪声效应与异步更新效应，我们采用同步更新方案让细胞自动机受噪声扰动。分析围绕针对α异步性的不同响应类别展开。我们依据异步条件下的行为修改程度，定义了4种噪声耐受等级，与我们提出的分类方案相契合。这4种用于对受噪声影响的系统进行分类的等级分别为：(i) φ不变类：可瞬时遗忘噪声带来的扰动的模型；(ii) φ-MR类：渐近细胞自动机间相关性≥0.5的模型；(iii) φ-LR类：扰动被限制在邻域内，但渐近细胞自动机间相关性<0.5的模型；(iv) φ依赖类：对噪声高度敏感，单次扰动即可引发行为显著变化的模型。
3. 文件夹「噪声与异步性」：我们分析了系统同时受异步性与噪声双重扰动时的行为修改程度。我们探究了分别对异步性或噪声具备鲁棒性/不变性的模型，在同时受两种扰动时的响应表现。我们的研究聚焦于两类细胞自动机：(i) α不变且φ不变的ECA，即规则0、32、128、160、250与254；(ii) α不变且φ-MR的ECA，即规则4、36、72、104、164与218。其余32种合法规则对应的系统对噪声和/或异步性较为敏感，不出所料，这类系统对双重扰动的鲁棒性较低。我们给出了同时受噪声影响的α异步系统与同步系统之间的渐近细胞自动机间相关性。不同异步率与噪声率的参数值以三维空间形式呈现，并投影至二维采样表面。