Critical properties of Rule 22 elementary cellular automata

The one-dimensional elementary cellular automaton Rule 22 is studied by means of Monte Carlo simulation on the dedicated K2 high-speed computer. If one considers random initialization with probability p for one-initialization per site, it is shown that the system behaves like a normal one-dimensional statistical ensemble with critical points atp=0 andp=1. Critical slowing down is exhibited, with a dynamical exponent of 1.0. The standard initialization ofp=0.5 is too far away from the critical point to allow similar observations.     

Recurrence properties of Lorentz lattice gas cellular automata

Recurrence properties of a point particle moving on a regular lattice randomly occupied with scatterers are studied for strictly deterministic, nondeterministic, and purely random scattering rules.On leave from Institute of Oceanology, USSR Academy of Sciences, 117218 Moscow, USSR     

Traveling waves and chaotic properties in cellular automata

Traveling wave solutions of cellular automata (CA) with two states and nearest neighbors interaction on one-dimensional (1-D) infinite lattice are computed. Space and time periods and the number of distinct waves have been computed for all representative rules, and each velocity ranging from 2 to 22. This computation shows a difference between spatially extended systems, generating only temporal chaos and those producing as well spatial complexity. In the first case wavelengths are simply related to the velocity of propagation and the dispersivity is an affine function, while in the second case (which coincides with Wolfram class 3), the dispersivity is multiform and its dependence on the velocities is highly random and discontinuous. This property is typical of space-time chaos in CA. (c) 1999 American Institute of Physics.     

Invariant strings and pattern-recognizing properties of one-dimensional cellular automata

A cellular automaton is a discrete dynamical system whose evolution is governed by a deterministic rule involving local interactions. It is shown that given an arbitrary string of values and an arbitrary neighborhood size (representing the range of interaction), a simple procedure can be used to find the rules of that neighborhood size under which the string is invariant. The set of nearestneighbor rules for which invariant strings exist is completely specified, as is the set of strings invariant under each such rule. For any automaton rule, an associated filtering rule is defined for which the only attractors are spatial sequences consisting of concatenations of invariant strings. A result is provided defining the rule of minimum neighborhood size for which an arbitrarily chosen string is the unique invariant string. The applications of filtering rules to pattern recognition problems are discussed.     

Ratchet cellular automata

In this work we propose a ratchet effect which provides a general means of performing clocked logic operations on discrete particles, such as single electrons or vortices. The states are propagated through the device by the use of an applied ac drive. We numerically demonstrate that a complete logic architecture is realizable using this ratchet. We consider specific nanostructured superconducting geometries using superconducting materials under an applied magnetic field, with the positions of the individual vortices in samples acting as the logic states. These devices can be used as the building blocks for an alternative microelectronic architecture.     

Magnetohydrodynamic cellular automata

A generalization of the hexagonal lattice gas model of Frisch, Hasslacher and Pomeau is shown to lead to two-dimensional magnetohydrodynamics. The method relies on the ideal point-wise conservation law for vector potential.     

Two-dimensional cellular automata

A largely phenomenological study of two-dimensional cellular automata is reported. Qualitative classes of behavior similar to those in one-dimensional cellular automata are found. Growth from simple seeds in two-dimensiona! cellular automata can produce patterns with complicated boundaries, characterized by a variety of growth dimensions. Evolution from disordered states can give domains with boundaries that execute effectively continuous motions. Some global properties of cellular automata can be described by entropies and Lyapunov exponents. Others are undecidable.This work was supported in part by the U.S. Office of Naval Research under Contract No. N00014-80-C-0657.     

Symplectic cellular automata

Cellular automata (CA) corresponding to hamiltonian mappings are proposed. The features of such CA are classified into the linear wave, superposed complex, and ergodic-like. It is shown that most nontrivial symplectic CA show the ergodic behavior. Spatio-temporal patterns, Poincaré's recurrence time, spatial entropies and Poincaré maps are calculated to confirm the ergodicity for the check of “ergodicity”. The variational principle for actions is discussed.     

Cylindrical cellular automata

A one-dimensional cellular automaton with periodic boundary conditions may be viewed as a lattice of sites on a cylinder evolving according to a local interaction rule. A technique is described for finding analytically the set of attractors for such an automaton. Given any one-dimensional automaton rule, a matrixA is defined such that the number of fixed points on an arbitrary cylinder size is given by the trace ofA ⁿ , where the powern depends linearly on the cylinder size. More generally, the number of strings of arbitrary length that appear in limit cycles of any fixed period is found as the solution of a linear recurrence relation derived from the characteristic equation of an associated matrix. The technique thus makes it possible, for any rule, to compute the number of limit cycles of any period on any cylinder size. To illustrate the technique, closed-form expressions are provided for the complete attractor structure of all two-neighbor rules. The analysis of attractors also identifies shifts as a basic mechanism underlying periodic behavior. Every limit cycle can be equivalently defined as a set of strings on which the action of the rule is a shift of sizes/h; i.e., each string cyclically shifts bys sites inh iterations of the rule. The study of shifts provides detailed information on the structure and number of limit cycles for one-dimensional automata.     

Thermal cellular automata fluids

The concepts of local temperature and local thermal equilibrium are introduced in the context of lattice gas cellular automata (LGGAs) whose dynamics conserves energy. Green-Kubo expressions for thermal transport coefficients, in particular for the heat conductivity, are derived in a form, equivalent to those for continuous fluids. All thermal transport coefficients are evaluated in Boltzmann approximation as thermal averages of matrix elements of the inverse Boltzmann collision operator, fully analogous to the results for continuous systems, and fully model-independent. The collision operator is expressed in terms of transition probabilities between in- and out-states. Staggered diffusivities arising from spuriously conserved quantities in LGCAs are also calculated. Examples of models with either cubic or hexagonal symmetries are discussed, where particles may or may not have internal energies.     

Deterministic one-dimensional cellular automata

A formal treatment of some of the properties of deterministic, rule 150, elementary one-dimensional cellular automata (CA) with null boundary conditions is presented. The general form of the characteristic polynomial of the CA global rule transition matrix is obtained. Mathematical relationships between the CA register lengths and the order of the corresponding group or semigroup structures are derived.     

Ergodicity of quantum cellular automata

We define a class of dynamical maps on the quasi-local algebra of a quantum spin system, which are quantum analoges of probabilistic cellular automata. We develop criteria for such a system to be ergodic, i.e., to posses a unique invariant state. Intuitively, ergodicity obtains if the local transition operators exhibit sufficiently large disorder. The ergodicity criteria also imply bounds for the exponential decay of correlations in the unique invariant state. The main technical tool is a quantum version of oscillation norms, defined in the classical case as the sum over all sites of the variations of an observable with respect to local spin flips.     

Phenomenology of nonlocal cellular automata

Dynamical systems with nonlocal connections have potential applications to economic and biological systems. This paper studies the dynamics of nonlocal cellular automata. In particular, all two-state, three-input nonlocal cellular automata are classified according to the dynamical behavior starting from random initial configurations and random wirings, although it is observed that sometimes a rule can have different dynamical behaviors with different wirings. The nonlocal cellular automata rule space is studied using a mean-field parametrization which is ideal for the situation of random wiring. Nonlocal cellular automata can be considered as computers carrying out computation at the level of each component. Their computational abilities are studied from the point of view of whether they contain many basic logical gates. In particular, I ask the question of whether a three-input cellular automaton rule contains the three fundamental logical gates: two-input rules AND and OR, and one-input rule NOT. A particularly interesting edge-of-chaos nonlocal cellular automaton, the rule 184, is studied in detail. It is a system of coupled selectors or multiplexers. It is also part of the Fredkin's gate—a proposed fundamental gate for conservative computations. This rule exhibits irregular fluctuations of density, large coherent structures, and long transient times.     

Periodic behavior of cellular automata

I propose an explanation of the observation of a globally synchronized behavior of deterministic cellular automata and coupled map lattices, together with local fluctuations.     

Internal symmetries of cellular automata

(Internal) transformations on the space Sigma of automaton configurations are defined as bi-infinite sequences of permutations of the cell symbols. A pair of transformations (gamma,theta) is said to be an internal symmetry of a cellular automaton f:Sigma-->Sigma if f=theta(-1)fgamma. It is shown that the full group of internal symmetries of an automaton f can be encoded as a group homomorphism F such that theta=F(gamma). The domain and image of the homomorphism F have, in general, infinite order and F is presented by a local automaton-like rule. Algorithms to compute the symmetry homomorphism F and to classify automata by their symmetries are presented. Examples on the types of dynamical implications of internal symmetries are discussed in detail. (c) 1997 American Institute of Physics.     

Phase transitions of cellular automata

Cellular automata (CA) are simple mathematical models of the dynamics of discrete variables in discrete space and time, with applications in nonequilibrium physics, chemical reactions, population dynamics and parallel computers. Phase transitions of stochastic CA with absorbing states are investigated. Using transfermatrix scaling the phase diagrams, critical properties and the entropy of one-dimensional CA are calculated. The corners of the phase diagrams reduce to deterministic CA discussed by Wolfram (Rev. Mod. Phys.55, 601 (1983)). Three-state models are introduced and, for special cases, exactly mapped onto two-state CA. The critical behaviour of other threestate models with one or two absorbing states and with immunization is investigated. Finally CA with competing reactions and/or with disorder are studied.