Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userInfinite Time Cellular Automata: A Real Computation Model
210
0
0.0
(
0
)
Authors
Fabien Givors
Ask ChatGPT about the research
No Arabic abstract
We define a new transfinite time model of computation, infinite time cellular automata. The model is shown to be as powerful than infinite time Turing machines, both on finite and infinite inputs; thus inheriting many of its properties. We then show how to simulate the canonical real computation model, BSS machines, with infinite time cellular automata in exactly omega steps.
rate research
Read More
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.
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 transmission of vector infectious diseases, which produces complex spatiotemporal patterns, is analyzed by a periodically forced two-dimensional cellular automata model. The system, which comprises three population levels, is introduced to describe complex features of the dynamics of the vector transmitted dengue epidemics, known to be very sensitive to seasonal variables. The three coupled levels represent the human, the adult and immature vector populations. The dynamics includes external seasonality forcing (rainfall intensity data), human and mosquito mobility, and vector control effects. The model parameters, even if bounded to well defined intervals obtained from reported data, can be selected to reproduce specific epidemic outbursts. In the current study, explicit results are obtained by comparison with actual data retrieved from the time-series of dengue epidemics in two cities in Brazil. The results show fluctuations that are not captured by mean-field models. It also reveals the qualitative behavior of the spatiotemporal patterns of the epidemics. In the extreme situation of absence of external periodic drive, the model predicts completely distinct long time evolution. The model is robust in the sense that it is able to reproduce the time series of dengue epidemics of different cities, provided the forcing term takes into account the local rainfall modulation. Finally, the dependence between epidemics threshold and vector control undergoes a transition from power law to stretched exponential behavior due to human mobility effect.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
