用转移矩阵法精确计算元胞自动机短轨迹数量,量化其动态行为。
Counting Short Trajectories in Elementary Cellular Automata using the Transfer Matrix Method
- 基于转移矩阵法,计算初始态在有限步内收敛到短吸引子的数量。
- 发现不同规则类的熵随时间演化特征:1类快速饱和,3类熵低且稳定。
- 为沃尔夫分类提供定量支撑,适合研究复杂系统动力学的学者参考。
元胞自动机(ECAs)表现出多样的行为,常按沃尔夫的定性分类进行划分。为建立对这些行为的定量理解,本文研究了此类自动机的全局动力学,并提出一种方法,可精确计算在有限时间步内收敛到短吸引子的所有初态数量。该计算在热力学极限(网格尺寸趋于无穷)下给出精确结果,基于我们为本任务定制的转移矩阵法(TMM)。具体而言,给定参数 $(p, c)$,可计算在 $p$ 步后收敛至大小为 $c$ 吸引子的初始配置的熵。通过对多种 ECA 规则进行此类统计,建立了熵与沃尔夫分类之间的定量联系:第1类规则随 $p$ 增大迅速趋于稳态($c=1$)的最大熵;第2类规则对合适周期 $c$ 也快速接近最大熵,可能需考虑平移;第3类规则表现出零或低有限熵,经短暂瞬态后饱和;第4类规则具有有限正熵,与某些第3类规则相似。该方法为轨迹统计提供了精确框架,但其在 $p+c$ 上的指数计算开销限制了实际分析仅限于短轨迹。
原文摘要 · Abstract (English)
Elementary Cellular Automata (ECAs) exhibit diverse behaviours often categorized by Wolfram's qualitative classification. To provide a quantitative basis for understanding these behaviours, we investigate the global dynamics of such automata and we describe a method that allows us to compute the number of all configurations leading to short attractors in a limited number of time steps. This computation yields exact results in the thermodynamic limit (as the CA grid size grows to infinity), and is based on the Transfer Matrix Method (TMM) that we adapt for our purposes. Specifically, given two parameters $(p, c)$ we are able to compute the entropy of all initial configurations converging to an attractor of size $c$ after $p$ time-steps. By calculating such statistics for various ECA rules, we establish a quantitative connection between the entropy and the qualitative Wolfram classification scheme. Class 1 rules rapidly converge to maximal entropy for stationary states ($c=1$) as $p$ increases. Class 2 rules also approach maximal entropy quickly for appropriate cycle lengths $c$, potentially requiring consideration of translations. Class 3 rules exhibit zero or low finite entropy that saturates after a short transient. Class 4 rules show finite positive entropy, similar to some Class 3 rules. This method provides a precise framework for quantifying trajectory statistics, although its exponential computational cost in $p+c$ restricts practical analysis to short trajectories.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。