Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userParity Problem With A Cellular Automaton Solution
132
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The parity of a bit string of length $N$ is a global quantity that can be efficiently compute using a global counter in ${O} (N)$ time. But is it possible to find the parity using cellular automata with a set of local rule tables without using any global counter? Here, we report a way to solve this problem using a number of $r=1$ binary, uniform, parallel and deterministic cellular automata applied in succession for a total of ${O} (N^2)$ time.
rate research
Read More
Given a continuous function $f(x)$, suppose that the sign of $f$ only has finitely many discontinuous points in the interval $[0,1]$. We show how to use a sequence of one dimensional deterministic binary cellular automata to determine the sign of $f(rho)$ where $rho$ is the (number) density of 1s in an arbitrarily given bit string of finite length provided that $f$ satisfies certain technical conditions.
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.
The problem `human and work in a model working group is investigated by means of cellular automata technique. Attitude of members of a group towards work is measured by an indicator of loyalty to the group (the number of agents who carry out their tasks), and lack of loyalty (the number of agents, who give their tasks to other agents). Initially, all agents realize scheduled tasks one-by-one. Agents with the number of scheduled tasks larger than a given threshold change their strategy to unloyal one and start avoiding completing tasks by passing them to their colleagues. Optionally, in some conditions, we allow agents to return to loyal state; hence the rule is hysteretic. Results are presented on an influence of i) the density of tasks, ii) the threshold number of tasks assigned to the agents forcing him/her for strategy change on the system efficiency. We show that a `black scenario of the system stacking in a `jammed phase (with all agents preferring unloyal strategy and having plenty tasks scheduled for realization) may be avoided when return to loyalty is allowed and either i) the number of agents chosen for task realization, or ii) the number of assigned tasks, or iii) the threshold value of assigned tasks, which force the agent to conversion from loyal strategy to unloyal one, or iv) the threshold value of tasks assigned to unloyal agent, which force him/her to task redistribution among his/her neighbors, are smartly chosen.
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.
In this paper, we explore the two-dimensional behavior of cellular automata with shuffle updates. As a test case, we consider the evacuation of a square room by pedestrians modeled by a cellular automaton model with a static floor field. Shuffle updates are characterized by a variable associated to each particle and called phase, that can be interpreted as the phase in the step cycle in the frame of pedestrian flows. Here we also introduce a dynamics for these phases, in order to modify the properties of the model. We investigate in particular the crossover between low- and high-density regimes that occurs when the density of pedestrians increases, the dependency of the outflow in the strength of the floor field, and the shape of the queue in front of the exit. Eventually we discuss the relevance of these results for pedestrians.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
