Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNumber conserving cellular automata: form decidability to dynamics
47
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We compare several definitions for number-conserving cellular automata that we prove to be equivalent. A necessary and sufficient condition for cas to be number-conserving is proved. Using this condition, we give a linear-time algorithm to decide number-conservation. The dynamical behavior of number-conserving cas is studied and a classification that focuses on chaoticity is given.
rate research
Read More
Gauge symmetries play a fundamental role in Physics, as they provide a mathematical justification for the fundamental forces. Usually, one starts from a non-interactive theory which governs `matter, and features a global symmetry. One then extends the theory so as make the global symmetry into a local one (a.k.a gauge-invariance). We formalise a discrete counterpart of this process, known as gauge extension, within the Computer Science framework of Cellular Automata (CA). We prove that the CA which admit a relative gauge extension are exactly the globally symmetric ones (a.k.a the colour-blind). We prove that any CA admits a non-relative gauge extension. Both constructions yield universal gauge-invariant CA, but the latter allows for a first example where the gauge extension mediates interactions within the initial CA.
We investigate number conserving cellular automata with up to five inputs and two states with the goal of comparing their dynamics with diffusion. For this purpose, we introduce the concept of decompression ratio describing expansion of configurations with finite support. We find that a large number of number-conserving rules exhibit abrupt change in the decompression ratio when the density of the initial pattern is increasing, somewhat analogous to the second order phase transition. The existence of this transition is formally proved for rule 184. Small number of rules exhibit infinite decompression ratio, and such rules may be useful for engineering of CA rules which are good models of diffusion, although they will most likely require more than two states.
The searching for the stable patterns in the evolution of cellular automata is implemented using stochastic synchronization between the present structures of the system and its precedent configurations. For most of the known evolution rules with complex behavior a dynamic competition among all the possible stable patterns is established and no stationary regime is reached. For the particular rule coded by the decimal number 18, a self-synchronization phenomenon can be obtained, even when strong modifications to the synchronization method are applied.
We present an intuitive formalism for implementing cellular automata on arbitrary topologies. By that means, we identify a symmetry operation in the class of elementary cellular automata. Moreover, we determine the subset of topologically sensitive elementary cellular automata and find that the overall number of complex patterns decreases under increasing neighborhood size in regular graphs. As exemplary applications, we apply the formalism to complex networks and compare the potential of scale-free graphs and metabolic networks to generate complex dynamics.
In this paper, linear Cellular Automta (CA) rules are recursively generated using a binary tree rooted at 0. Some mathematical results on linear as well as non-linear CA rules are derived. Integers associated with linear CA rules are defined as linear numbers and the properties of these linear numbers are studied.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
