Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComputational Hierarchy of Elementary Cellular Automata
157
0
0.0
(
0
)
Added by
Barbora Hudcova
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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 automata 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.
rate research
Read More
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.
Coronavirus disease (COVID-19) which is caused by SARS-COV2 has become a pandemic. This disease is highly infectious and potentially fatal, causing a global public health concern. To contain the spread of COVID-19, governments are adopting nationwide interventions, like lockdown, containment and quarantine, restrictions on travel, cancelling social events and extensive testing. To understand the effects of these measures on the control of the epidemic in a data-driven manner, we propose a probabilistic cellular automata (PCA) based modified SEIQR model. The transitions associated with the model is driven by data available on chronology, symptoms, pathogenesis and transmissivity of the virus. By arguing that the lattice-based model captures the features of the dynamics along with the existing fluctuations, we perform rigorous computational analyses of the model to take into account of the spatial dynamics of social distancing measures imposed on the people. Considering the probabilistic behavioural aspects associated with mitigation strategies, we study the model considering factors like population density and testing efficiency. Using the model, we focus on the variability of epidemic dynamics data for different countries and point out the reasons behind these contrasting observations. To the best of our knowledge, this is the first attempt to model COVID-19 spread using PCA that gives us both spatial and temporal variations of the infection spread with the insight about the contributions of different infection parameters.
With the advent of huges volumes of data produced in the form of fast streams, real-time machine learning has become a challenge of relevance emerging in a plethora of real-world applications. Processing such fast streams often demands high memory and processing resources. In addition, they can be affected by non-stationary phenomena (concept drift), by which learning methods have to detect changes in the distribution of streaming data, and adapt to these evolving conditions. A lack of efficient and scalable solutions is particularly noted in real-time scenarios where computing resources are severely constrained, as it occurs in networks of small, numerous, interconnected processing units (such as the so-called Smart Dust, Utility Fog, or Swarm Robotics paradigms). In this work we propose LUNAR, a streamified version of cellular automata devised to successfully meet the aforementioned requirements. It is able to act as a real incremental learner while adapting to drifting conditions. Extensive simulations with synthetic and real data will provide evidence of its competitive behavior in terms of classification performance when compared to long-established and successful online learning methods.
A novel, information-based classification of elementary cellular automata is proposed that circumvents the problems associated with isolating whether complexity is in fact intrinsic to a dynamical rule, or if it arises merely as a product of a complex initial state. Transfer entropy variations processed by the system split the 256 elementary rules into three information classes, based on sensitivity to initial conditions. These classes form a hierarchy such that coarse-graining transitions observed among elementary cellular automata rules predominately occur within each information- based class, or much more rarely, down the hierarchy.
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.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
