Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCellular Automata Rules and Linear Numbers
161
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
Recent experiments by Springer and Kenyon have shown that a deep neural network can be trained to predict the action of $t$ steps of Conways Game of Life automaton given millions of examples of this action on random initial states. However, training was never completely successful for $t>1$, and even when successful, a reconstruction of the elementary rule ($t=1$) from $t>1$ data is not within the scope of what the neural network can deliver. We describe an alternative network-like method, based on constraint projections, where this is possible. From a single data item this method perfectly reconstructs not just the automaton rule but also the states in the time steps it did not see. For a unique reconstruction, the size of the initial state need only be large enough that it and the $t-1$ states it evolves into contain all possible automaton input patterns. We demonstrate the method on 1D binary cellular automata that take inputs from $n$ adjacent cells. The unknown rules in our experiments are not restricted to simple rules derived from a few linear functions on the inputs (as in Game of Life), but include all $2^{2^n}$ possible rules on $n$ inputs. Our results extend to $n=6$, for which exhaustive rule-search is not feasible. By relaxing translational symmetry in space and also time, our method is attractive as a platform for the learning of binary data, since the discreteness of the variables does not pose the same challenge it does for gradient-based methods.
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.
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.
Emergent processes in complex systems such as cellular automata can perform computations of increasing complexity, and could possibly lead to artificial evolution. Such a feat would require scaling up current simulation sizes to allow for enough computational capacity. Understanding complex computations happening in cellular automata and other systems capable of emergence poses many challenges, especially in large-scale systems. We propose methods for coarse-graining cellular automata based on frequency analysis of cell states, clustering and autoencoders. These innovative techniques facilitate the discovery of large-scale structure formation and complexity analysis in those systems. They emphasize interesting behaviors in elementary cellular automata while filtering out background patterns. Moreover, our methods reduce large 2D automata to smaller sizes and enable identifying systems that behave interestingly at multiple scales.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
