Lei Qin, Lee Jia, Huang Xin, Kawasaki Shuji
College of Computer Science, Chongqing University, Chongqing 400044, China.
Chong Key Laboratory of Software Theory and Technology, Chongqing 400044, China.
Entropy (Basel). 2021 Feb 8;23(2):209. doi: 10.3390/e23020209.
Classification of asynchronous elementary cellular automata (AECAs) was explored in the first place by Fates et al. (Complex Systems, 2004) who employed the asymptotic density of cells as a key metric to measure their robustness to stochastic transitions. Unfortunately, the asymptotic density seems unable to distinguish the robustnesses of all AECAs. In this paper, we put forward a method that goes one step further via adopting a metric entropy (Martin, Complex Systems, 2000), with the aim of measuring the asymptotic mean entropy of local pattern distribution in the cell space of any AECA. Numerical experiments demonstrate that such an entropy-based measure can actually facilitate a complete classification of the robustnesses of all AECA models, even when all local patterns are restricted to length 1. To gain more insights into the complexity concerning the forward evolution of all AECAs, we consider another entropy defined in the form of Kolmogorov-Sinai entropy and conduct preliminary experiments on classifying their uncertainties measured in terms of the proposed entropy. The results reveal that AECAs with low uncertainty tend to converge remarkably faster than models with high uncertainty.
异步初等元胞自动机（AECAs）的分类最初是由法特斯等人（《复杂系统》，2004年）进行探索的，他们采用细胞的渐近密度作为关键指标来衡量其对随机转变的稳健性。不幸的是，渐近密度似乎无法区分所有AECAs的稳健性。在本文中，我们提出了一种通过采用度量熵（马丁，《复杂系统》，2000年）进一步深入的方法，旨在测量任何AECA细胞空间中局部模式分布的渐近平均熵。数值实验表明，这种基于熵的度量实际上可以促进对所有AECA模型稳健性的完整分类，即使所有局部模式都限制为长度1。为了更深入地了解所有AECAs正向演化的复杂性，我们考虑以柯尔莫哥洛夫-西奈熵形式定义的另一种熵，并对根据所提出的熵测量的其不确定性进行分类的初步实验。结果表明，不确定性低的AECAs比不确定性高的模型收敛速度明显更快。
