Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Particular Universal Cellular Automaton
272
0
0.0
(
0
)
Added by
EPTCS
Publication date
2009
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Signals are a classical tool used in cellular automata constructions that proved to be useful for language recognition or firing-squad synchronisation. Particles and collisions formalize this idea one step further, describing regular nets of colliding signals. In the present paper, we investigate the use of particles and collisions for constructions involving an infinite number of interacting particles. We obtain a high-level construction for a new smallest intrinsically universal cellular automaton with 4 states.
rate research
Read More
This talk advocates intrinsic universality as a notion to identify simple cellular automata with complex computational behavior. After an historical introduction and proper definitions of intrinsic universality, which is discussed with respect to Turing and circuit universality, we discuss construction methods for small intrinsically universal cellular automata before discussing techniques for proving non universality.
Gliders in one-dimensional cellular automata are compact groups of non-quiescent and non-ether patterns (ether represents a periodic background) translating along automaton lattice. They are cellular-automaton analogous of localizations or quasi-local collective excitations travelling in a spatially extended non-linear medium. They can be considered as binary strings or symbols travelling along a one-dimensional ring, interacting with each other and changing their states, or symbolic values, as a result of interactions. We analyse what types of interaction occur between gliders travelling on a cellular automaton `cyclotron and build a catalog of the most common reactions. We demonstrate that collisions between gliders emulate the basic types of interaction that occur between localizations in non-linear media: fusion, elastic collision, and soliton-like collision. Computational outcomes of a swarm of gliders circling on a one-dimensional torus are analysed via implementation of cyclic tag systems.
In this paper, we study reversibility of one-dimensional(1D) linear cellular automata(LCA) under null boundary condition, whose core problems have been divided into two main parts: calculating the period of reversibility and verifying the reversibility in a period. With existing methods, the time and space complexity of these two parts are still too expensive to be employed. So the process soon becomes totally incalculable with a slightly big size, which greatly limits its application. In this paper, we set out to solve these two problems using two efficient algorithms, which make it possible to solve reversible LCA of very large size. Furthermore, we provide an interesting perspective to conversely generate 1D LCA from a given period of reversibility. Due to our methods efficiency, we can calculate the reversible LCA with large size, which has much potential to enhance security in cryptography system.
The aim of this paper is to investigate whether the class of automaton semigroups is closed under certain semigroup constructions. We prove that the free product of two automaton semigroups that contain left identities is again an automaton semigroup. We also show that the class of automaton semigroups is closed under the combined operation of free product followed by adjoining an identity. We present an example of a free product of finite semigroups that we conjecture is not an automaton semigroup. Turning to wreath products, we consider two slight generalizations of the concept of an automaton semigroup, and show that a wreath product of an automaton monoid and a finite monoid arises as a generalized automaton semigroup in both senses. We also suggest a potential counterexample that would show that a wreath product of an automaton monoid and a finite monoid is not a necessarily an automaton monoid in the usual sense.
A cellular automaton model of pulsar glitches is described, based on the superfluid vortex unpinning paradigm. Recent analyses of pulsar glitch data suggest that glitches result from scale-invariant avalanches citep{Melatos07a}, which are consistent with a self-organized critical system (SOCS). A cellular automaton provides a computationally efficient means of modelling the collective behaviour of up to $10^{16}$ vortices in the pulsar interior, whilst ensuring that the dominant aspects of the microphysics are not lost. The automaton generates avalanche distributions that are qualitatively consistent with a SOCS and with glitch data. The probability density functions of glitch sizes and durations are power laws, and the probability density function of waiting times between successive glitches is Poissonian, consistent with statistically independent events. The output of the model depends on the physical and computational paramters used. The fitted power law exponents for the glitch sizes ($a$) and durations ($b$) decreases as the strength of the vortex pinning increases. Similarly the exponents increase as the fraction of vortices that are pinned decreases. For the physical and computational parameters considered, one finds $-4.3leq a leq -2.0$ and $-5.5leq bleq -2.2$, and mean glitching rates in the range $0.0023leqlambdaleq0.13$ in units of inverse time.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
