The kink of cellular automaton rule 18 performs a random walk

We give an exact characterization of the movement of a single kink in the elementary cellular automaton Rule 18. It is a random walk with independent increments as well as independent delay times. Its statistical parameters are computed to confirm the earlier simulation results by Grassberger.     

A percolation approach to the Kauffman model

A study is made of the spreading of damage in the random but deterministic Kauffman model on the square lattice with the spreading from one edge of the lattice. The critical value of the parameterp _c above which the system becomes chaotic is found to bep _c0.298. The possibility of suppression of the chaotic phase by noise is also studied. It is found that forpp _c, an extremely large noise levelg>0.99 is required, if possible at all.On leave from Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing, China.     

Kinetic limits of the HPP cellular automaton

We study the Boltzmann-Grad limit in various versions of the two-dimensional HPP cellular automaton. In the completely deterministic case we prove convergence to an evolution that is not of kinetic type, a well-known phenomenon after Uchyiama's paper on the Broadwell gas, whereas the limiting equation becomes of kinetic type in the model with random collisions. The main part of the paper concerns the case where the collisions are deterministic and the randomness comes from inserting, between any two successive HPP updatings, ^- stirring updatings, <1 being any fixed positive number and a parameter which tends to 0. The initial measure is a product measure with average occupation numbers of the order of (low-density limit) and varying on distances of the order of ^–1. The limit as 0 of the system evolved for times of the order of ^-1- corresponds to the Boltzmann-Grad limit. We prove propagation of chaos and that the renormalized average occupation numbers (i.e., divided by) converge to the solution of the Broadwell equation. Convergence is proven at all times for which the solution of the Broadwell equation is bounded.     

The Domany-Kinzel cellular automaton phase diagram

The boundaries between the three phases of the Domany-Kinzel probabilistic cellular automaton are determined with high accuracy via the gradient method. The difficulties the extrapolation to the thermodynamic limit are circumvented and the critical exponents are also presented.     

Long-range effects in an elementary cellular automaton

We present evidence that one of the elementary one-dimensional cellular automata in the sense of Wolfram (rule 22 in Wolfram's notation) involves very complex long-range effects, similar to a critical phenomenon. This is in contrast to superficial evidence that would suggest that this rule leads to fairly simple behavior.     

Quantum walks and reversible cellular automata

We obtain a conserved quantity for a reversible cellular automaton derived from a discrete-time quantum walk in one dimension. As a corollary, we give detailed information regarding the evolution of the quantum walk.     

Quantum cellular automaton theory of light

We present a quantum theory of light based on the recent derivation of Weyl and Dirac quantum fields from general principles ruling the interactions of a countable set of abstract quantum systems, without using space–time and mechanics (D’Ariano and Perinotti, 2014). In a Planckian interpretation of the discreteness, the usual quantum field theory corresponds to the so-called relativistic regime of small wave-vectors. Within the present framework the photon is a composite particle made of an entangled pair of free Weyl Fermions, and the usual Bosonic statistics is recovered in the low photon density limit, whereas the Maxwell equations describe the relativistic regime. We derive the main phenomenological features of the theory in the ultra-relativistic regime, consisting in a dispersive propagation in vacuum, and in the occurrence of a small longitudinal polarization, along with a saturation effect originated by the Fermionic nature of the photon. We then discuss whether all these effects can be experimentally tested, and observe that only the dispersive effects are accessible to the current technology via observations of gamma-ray bursts.     

Critical points of two-dimensional bootstrap percolation-like cellular automata

Cellular automata in two dimensions that generalize the bootstrap percolation dynamics are considered, focusing on the thresholdp _c of the initial density for convergence to total occupancy to occur; these models are classified according top _c being 0, 1, or strictly between these extreme values. Explicit upper and lower bounds are provided in the third case.     

Exact results for deterministic cellular automata with additive rules

Deterministic cellular automata (CA) with additive rules are studied by exploiting the properties of circulant matrices on finite fields. Complete state transition diagrams for higher-order and multidimensional CA on finite lattices are analyzed. Conditions on the rules which make them reversible are obtained. It is shown that all state transition diagrams of the CA have identical trees rooted on cycles. General formulae for cycle lengths and multiplicities are given.     

The Gacs-Kurdyumov-Levin automaton revisited

We study a one-dimensional cellular automaton that was originally proposed as a candidate for exhibiting nonergodic behavior under noise. We prove that the deterministic model has the eroder property for two and only two invariant states. Moreover, we give the best possible estimates for the corresponding erosion times. We then review the results we have obtained from extensive computer simulations for the stochastic model and for a mixed model and argue that they suggest numerical and heuristic evidence in favour of ergodic behavior for all nonzero values of the noise parameter.     

An improved cellular automaton traffic model considering gap-dependent delay probability

In this paper, the delay probability of the original Nagel and Schreckenberg model is modified to simulate one-lane traffic flow. The delay probability of a vehicle depends on its corresponding gap. According to simulation results, it has been found that the structure of the fundamental diagram of the new model is sensitively dependent on the values of the delay probability. In comparison with the NS model, one notes that the fundamental diagram of the new model is more consistent with the results measured in the real traffic, and the velocity distributions of the new model are relatively reasonable.     

Calibrating cellular automaton models for pedestrians walking through corners

Cellular Automata (CA) based pedestrian simulation models have gained remarkable popularity as they are simpler and easier to implement compared to other microscopic modeling approaches. However, incorporating traditional floor field representations in CA models to simulate pedestrian corner navigation behavior could result in unrealistic behaviors. Even though several previous studies have attempted to enhance CA models to realistically simulate pedestrian maneuvers around bends, such modifications have not been calibrated or validated against empirical data. In this study, two static floor field (SFF) representations, namely ‘discrete representation’ and ‘continuous representation’, are calibrated for CA-models to represent pedestrians' walking behavior around 90° bends. Trajectory data collected through a controlled experiment are used to calibrate these model representations. Calibration results indicate that although both floor field representations can represent pedestrians' corner navigation behavior, the ‘continuous’ representation fits the data better. Output of this study could be beneficial for enhancing the reliability of existing CA-based models by representing pedestrians' corner navigation behaviors more realistically.     

The dynamics of defect ensembles in one-dimensional cellular automata

We investigate the dynamics of ensembles of diffusive defects in one-dimensional deterministic cellular automata. The work builds on earlier results on individual random walks in cellular automata. Here we give a natural condition guaranteeing diffusive behavior also in the presence of other defects. Simple branching and birth mechanisms are introduced and prototype classes of cellular automata exhibiting weakly interacting walks capable of annihilation and coalescence are studied. Their equilibrium behavior is also characterized. The design principles of cellular automata with desired diffusive interaction properties become transparent from this analysis.     

Cellular automaton model for evacuation process with obstacles

A bidimensional cellular automaton model is used to simulate the process of evacuation of pedestrians in a room with fixed obstacles. A floor field is defined so that moving to a cell with lower floor field means approaching an exit door. The model becomes non-deterministic by introducing a “panic” parameter, given by a probability of not moving, and by a random choice to resolve conflicts in the update of pedestrian positions. Two types of exit doors are considered: single (where only one person can pass) and double (two persons can pass simultaneously). For a double door, the longest evacuation time turns out to occur for a very traditional location of the door. The optimum door position is determined. Replacing the double door by two single doors does not improve evacuation times noticeably. On the other hand, for a room without obstacles, a simple scaling law is proposed to model the dependence of evacuation time with the number of persons and exit width. This model fails when obstacles are present, as their presence introduces local bottlenecks whose effect outweighs the benefits of increasing door width beyond a certain threshold.     

The existence of phase V in the Mandelbrot percolation process

Dekking and Meester defined six phases for a subclass of random Cantor sets consisting of those generated by Bernoulli random substitutions. They proved that the random Sierpinski carpet passed through all these phases asp tended from 0 to 1, but the were not able to prove the existencne of phase V in the Mandelbrot percolation process. In this paper, we accomplish the proof by improving their methods.Research supported by the Chinese Natural Science Foundation.     

Covering by random intervals and one-dimensional continuum percolation

A brief historical introduction is given to the problem of covering a line by random overlapping intervals. The problem for equal intervals was first solved by Whitworth in the 1890s. A brief resume is given of his solution. The advantages of the present author's approach, which uses a Poisson process, are outlined, and a solution is derived by Laplace transforms. The method of Hammersley for dealing with a stochastic distribution of intervals is described, and a solution can still be derived by Laplace transforms. The asymptotic behavior as the line becomes long is calculated and is related to the one-dimensional continuum percolation problem. It is shown that as long as the mean interval size is finite, the probability of complete coverage decays exponentially, so that the critical percolation probabilityp _c =1. However, as soon as the mean interval size becomes infinite, the critical percolation probabilityp _c switches to 0. This is in accord with previous results for a lattice model by Chinese workers, but differs from those of Schulman. A possible reason for the discrepancy is a difference in boundary conditions.On sabbatical leave from Physics Department, Bar Ilan University, Ramat Gan, Israel.     

逾渗分立时间量子行走的传输及纠缠特性

在一维分立时间量子行走中,通过静态和动态两种方式随机地断开连接边引入无序效应,研究了静态逾渗和动态逾渗对量子行走传输特性以及位置自由度和硬币自由之间纠缠的影响.随着演化时间的增加,静态逾渗会使得量子行走从弹道传输转变为安德森局域化,而动态逾渗则会使之转变为经典扩散.理想情况下,量子纠缠在较短的时间内就达到一个常数值E_0.静态逾渗量子行走的纠缠减小,并随着时间做无规振荡,而动态逾渗量子行走的纠缠则会随着时间光滑地增加,并在某一时间超过理想情况下的常数值,表现出动态逾渗增强量子纠缠的特性.     

Energy transport in a cellular automaton

Energy transport in the deterministic Q2R cellular automaton is studied. Two different types of transport processes are found: a diffusion type and a very efficient transport on “highways.” The dependence of both types on the energy is investigated.     

Anomalous diffusion and continuum percolation

Anomalous diffusion for continuum percolation is simulated by considering systems of randomly distributed circles and spheres. Universal behavior is obtained for the case of equal local conductances and nonuniversal behavior for diverging distributions of the local conductances. Diffusion in the continuum has a behavior consistent with that of other transport properties in the continuum. In addition, the results suggest that different algorithms for diffusion, which differ only in the random walker sitting times, are equivalent.