ترغب بنشر مسار تعليمي؟ اضغط هنا

Long-range memory elementary 1D cellular automata: Dynamics and nonextensivity

102   0   0.0 ( 0 )
 نشر من قبل Thimo Rohlf
 تاريخ النشر 2006
  مجال البحث فيزياء
والبحث باللغة English




اسأل ChatGPT حول البحث

We numerically study the dynamics of elementary 1D cellular automata (CA), where the binary state $sigma_i(t) in {0,1}$ of a cell $i$ does not only depend on the states in its local neighborhood at time $t-1$, but also on the memory of its own past states $sigma_i(t-2), sigma_i(t-3),...,sigma_i(t-tau),...$. We assume that the weight of this memory decays proportionally to $tau^{-alpha}$, with $alpha ge 0$ (the limit $alpha to infty$ corresponds to the usual CA). Since the memory function is summable for $alpha>1$ and nonsummable for $0le alpha le 1$, we expect pronounced %qualitative and quantitative changes of the dynamical behavior near $alpha=1$. This is precisely what our simulations exhibit, particularly for the time evolution of the Hamming distance $H$ of initially close trajectories. We typically expect the asymptotic behavior $H(t) propto t^{1/(1-q)}$, where $q$ is the entropic index associated with nonextensive statistical mechanics. In all cases, the function $q(alpha)$ exhibits a sensible change at $alpha simeq 1$. We focus on the class II rules 61, 99 and 111. For rule 61, $q = 0$ for $0 le alpha le alpha_c simeq 1.3$, and $q<0$ for $alpha> alpha_c$, whereas the opposite behavior is found for rule 111. For rule 99, the effect of the long-range memory on the spread of damage is quite dramatic. These facts point at a rich dynamics intimately linked to the interplay of local lookup rules and the range of the memory. Finite size scaling studies varying system size $N$ indicate that the range of the power-law regime for $H(t)$ typically diverges $propto N^z$ with $0 le z le 1$. Similar studies have been carried out for other rules, e.g., the famous universal computer rule 110.



قيم البحث

اقرأ أيضاً

The complexity of cellular automata is traditionally measured by their computational capacity. However, it is difficult to choose a challenging set of computational tasks suitable for the parallel nature of such systems. We study the ability of autom ata to emulate one another, and we use this notion to define such a set of naturally emerging tasks. We present the results for elementary cellular automata, although the core ideas can be extended to other computational systems. We compute a graph showing which elementary cellular automata can be emulated by which and show that certain chaotic automata are the only ones that cannot emulate any automata non-trivially. Finally, we use the emulation notion to suggest a novel definition of chaos that we believe is suitable for discrete computational systems. We believe our work can help design parallel computational systems that are Turing-complete and also computationally efficient.
A generalized set of Clifford cellular automata, which includes all Clifford cellular automata, result from the quantization of a lattice system where on each site of the lattice one has a $2k$-dimensional torus phase space. The dynamics is a linear map in the torus variables and it is also local: the evolution depends only on variables in some region around the original lattice site. Moreover it preserves the symplectic structure. These are classified by $2ktimes 2k$ matrices with entries in Laurent polynomials with integer coefficients in a set of additional formal variables. These can lead to fractal behavior in the evolution of the generators of the quantum algebra. Fractal behavior leads to non-trivial Lyapunov exponents of the original linear dynamical system. The proof uses Fourier analysis on the characteristic polynomial of these matrices.
In this paper, we study reversibility of one-dimensional(1D) linear cellular automata(LCA) under null boundary condition, whose core problems have been divided into two main parts: calculating the period of reversibility and verifying the reversibili ty in a period. With existing methods, the time and space complexity of these two parts are still too expensive to be employed. So the process soon becomes totally incalculable with a slightly big size, which greatly limits its application. In this paper, we set out to solve these two problems using two efficient algorithms, which make it possible to solve reversible LCA of very large size. Furthermore, we provide an interesting perspective to conversely generate 1D LCA from a given period of reversibility. Due to our methods efficiency, we can calculate the reversible LCA with large size, which has much potential to enhance security in cryptography system.
197 - Nicolas Ollinger 2019
This paper studies three classes of cellular automata from a computational point of view: freezing cellular automata where the state of a cell can only decrease according to some order on states, cellular automata where each cell only makes a bounded number of state changes in any orbit, and finally cellular automata where each orbit converges to some fixed point. Many examples studied in the literature fit into these definitions, in particular the works on cristal growth started by S. Ulam in the 60s. The central question addressed here is how the computational power and computational hardness of basic properties is affected by the constraints of convergence, bounded number of change, or local decreasing of states in each cell. By studying various benchmark problems (short-term prediction, long term reachability, limits) and considering various complexity measures and scales (LOGSPACE vs. PTIME, communication complexity, Turing computability and arithmetical hierarchy) we give a rich and nuanced answer: the overall computational complexity of such cellular automata depends on the class considered (among the three above), the dimension, and the precise problem studied. In particular, we show that all settings can achieve universality in the sense of Blondel-Delvenne-Kr{u}rka, although short term predictability varies from NLOGSPACE to P-complete. Besides, the computability of limit configurations starting from computable initial configurations separates bounded-change from convergent cellular automata in dimension 1, but also dimension 1 versus higher dimensions for freezing cellular automata. Another surprising dimension-sensitive result obtained is that nilpotency becomes decidable in dimension 1 for all the three classes, while it stays undecidable even for freezing cellular automata in higher dimension.
161 - Salvatore Miccich`e 2008
In this paper we give explicit examples of power-law correlated stationary Markovian processes y(t) where the stationary pdf shows tails which are gaussian or exponential. These processes are obtained by simply performing a coordinate transformation of a specific power-law correlated additive process x(t), already known in the literature, whose pdf shows power-law tails 1/x^a. We give analytical and numerical evidence that although the new processes (i) are Markovian and (ii) have gaussian or exponential tails their autocorrelation function still shows a power-law decay <y(t) y(t+T)>=1/T^b where b grows with a with a law which is compatible with b=a/2-c, where c is a numerical constant. When a<2(1+c) the process y(t), although Markovian, is long-range correlated. Our results help in clarifying that even in the context of Markovian processes long-range dependencies are not necessarily associated to the occurrence of extreme events. Moreover, our results can be relevant in the modeling of complex systems with long memory. In fact, we provide simple processes associated to Langevin equations thus showing that long-memory effects can be modeled in the context of continuous time stationary Markovian processes.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا