اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدInfinite Time Cellular Automata: A Real Computation Model
214
0
0.0
(
0
)
تأليف
Fabien Givors
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 comp
utational 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 th
e 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 configuration
s 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 descri
be 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 e
lementary 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
