Toom's rule

Last updated January 06, 2024

Toom's rule is a 2-dimensional cellular automaton model created by Andrei Toom in 1978.^[1]^[2] It is a modification of the 2-dimensional majority vote rule and can have more robust memory when considered as a thermal physical system in statistical field theory.^[3] The model also has a noise-dependent phase transition.^[1]

Statement

Toom's rule is a cellular automaton that acts on a 2-dimensional square lattice. At each site in this lattice is a spin with the value +1 or -1. At time $t=0$ the bits are initialized to some value. At each discrete time step $(t>0)$ the lattice evolves according to Toom's rule. This rule is applied at each site simultaneously.

A deterministic version of Toom's rule can be stated as:

At each site in the lattice if the spin of the current (center) site plus the neighboring spin to the North plus the neighboring spin to the East is greater than 0, then the current spin becomes +1 in the next time step.
If this sum is less than 0, then the current spin becomes -1 in the next time step. As there are 3 spins the sum can never equal 0.

Toom's rule is sometimes called the NEC rule since it involves the North, East, and Center sites.^[1]

The general version of Toom's rule is probabilistic and can be stated as:

Apply the deterministic version of Toom's rule.
If step 1 results in a spin of +1 change it to -1 with probability q. Otherwise, if step 2 results in a spin of -1 change it to +1 with probability p.^[4]

The deterministic version can be recovered by setting p=q=0.

Toom's rule is an example of a probabilistic cellular automata (see Stochastic cellular automaton), defined on the lattice $\mathbb {Z} ^{2}$ .^[1]

Properties

When $p\neq q$ the system will tend to favor one spin over the other, which can be interpreted as the effect of a magnetic field.^[1]

The model has a phase transition. For low enough p, q, there are at least two steady states, but for high enough p, q, there is a unique steady state.^[1] This is proven in Toom's original paper.^[2]

When p=q=0, there is a steady state with a staircase-like boundary (interface) between +1 and -1 spins. When p, q are small, there are fluctuations along this interface. Additional models have been built to study the interface dynamics as a 1D spin configuration (on $\mathbb {Z} _{+}$ ).

One can define $\lambda _{+}$ as the rate (probability) that each +1 exchanges places with the first -1 spin on its right. The rate $\lambda _{-}$ can be defined similarly. One can make a further simplification that only the leftmost spin in a block (of identical spins) exchanges places with the first opposite spin to the right. Also, let the first spin flip independently with probability $\alpha$ . This 1D model has also been called Toom's rule.^[1]

When studying the steady state where $\lambda _{+}=\lambda _{-}=\alpha$ , the density of site n (the expected value of site n) follows the scale law:^[1]

$\langle \sigma _{n}\rangle \sim {\frac {1}{2{\sqrt {\pi n}}}}$

One can also define a finite version of this 1D Toom's rule where there are L sites (finite interface model). The leftmost -1 in a block exchanges with the first +1 to the right with probability $\alpha$ , and the leftmost +1 in a block exchanges with the first -1 to the right with probability $\beta$ . In this model, there are u up spins and d down spins where u+d=L. There are also ${\binom {L}{u}}$ configurations of the L sites.^[1]

The correlation functions, partition function, Markov Matrices, and their eigenvalues can be computed for this finite Toom rule. It has been shown that when $\alpha =\beta$ and large n < L, the density function follows the same inverse square law as above: $\langle \sigma _{n}\rangle \sim {\frac {1}{2{\sqrt {\pi n}}}}$ .

When $\alpha \neq \beta$ it is conjectured that the density decays like 1/n.^[1]

Toom's rule as a memory

Toom's rule is a dynamical variant of the Ising model. There are many dynamical rules for the Ising model where the steady state is Gibbsian.^[1]

The 2-dimensional ferromagnetic Ising model in the absence of local magnetic fields has two ground states: one with all spins in the lattice having +1 (spin up) and the other with all spins in the lattice having -1 (spin down). For this reason, the 2D Ising model can be seen as a memory storing one bit of information in the ground state.

This memory is robust in the sense that if errors cause some spins to flip, returning to the ground state will preserve the stored information. These errors occur due to thermal noise in the system. Therefore it is said this memory is robust in the presence of thermal noise. However, if there is a local magnetic field which favors one ground state over the other, then the Ising model is no longer a reliable memory since there is only one ground state.

The 2-dimensional majority vote cellular automaton (CA) is analogous to the Ising model. The majority vote CA evolves each site in the lattice by taking the spin value of current site plus that of the 4 neighboring sites and makes this spin +1 in the next time step if the sum is positive and -1 if the sum is negative. Just as for Toom's rule we can construct a probabilistic version of the majority vote CA where the output can be changed with probability q from spin +1 to spin -1 and with probability p from spin -1 to a spin +1.

Instead of ground states, information is stored in stable states of the CA. These are states such that the spins on the lattice do not change when acted upon by the CA. It is easy to show that the all +1 and the all -1 states are stable states when q=p=0. Therefore the majority vote CA can be used to store information. We can define terms analogous to thermal noise and magnetic field as T=p+q and h=(p-q)/(p+q) respectively. Similarly to the Ising model the majority vote CA can reliably store information for small values of T. Unlike the Ising mode, if T is small enough, this is even true for arbitrary values of h.^[4]^[5]

Toom's model can be applied to fault-tolerant computation.^[5]

Related Research Articles

In probability theory and statistics, the exponential distribution or negative exponential distribution is the probability distribution of the time between events in a Poisson point process, i.e., a process in which events occur continuously and independently at a constant average rate. It is a particular case of the gamma distribution. It is the continuous analogue of the geometric distribution, and it has the key property of being memoryless. In addition to being used for the analysis of Poisson point processes it is found in various other contexts.

<span class="mw-page-title-main">Lattice model (physics)</span>

In mathematical physics, a lattice model is a mathematical model of a physical system that is defined on a lattice, as opposed to a continuum, such as the continuum of space or spacetime. Lattice models originally occurred in the context of condensed matter physics, where the atoms of a crystal automatically form a lattice. Currently, lattice models are quite popular in theoretical physics, for many reasons. Some models are exactly solvable, and thus offer insight into physics beyond what can be learned from perturbation theory. Lattice models are also ideal for study by the methods of computational physics, as the discretization of any continuum model automatically turns it into a lattice model. The exact solution to many of these models includes the presence of solitons. Techniques for solving these include the inverse scattering transform and the method of Lax pairs, the Yang–Baxter equation and quantum groups. The solution of these models has given insights into the nature of phase transitions, magnetization and scaling behaviour, as well as insights into the nature of quantum field theory. Physical lattice models frequently occur as an approximation to a continuum theory, either to give an ultraviolet cutoff to the theory to prevent divergences or to perform numerical computations. An example of a continuum theory that is widely studied by lattice models is the QCD lattice model, a discretization of quantum chromodynamics. However, digital physics considers nature fundamentally discrete at the Planck scale, which imposes upper limit to the density of information, aka Holographic principle. More generally, lattice gauge theory and lattice field theory are areas of study. Lattice models are also used to simulate the structure and dynamics of polymers.

The Ising model, named after the physicists Ernst Ising and Wilhelm Lenz, is a mathematical model of ferromagnetism in statistical mechanics. The model consists of discrete variables that represent magnetic dipole moments of atomic "spins" that can be in one of two states. The spins are arranged in a graph, usually a lattice, allowing each spin to interact with its neighbors. Neighboring spins that agree have a lower energy than those that disagree; the system tends to the lowest energy but heat disturbs this tendency, thus creating the possibility of different structural phases. The model allows the identification of phase transitions as a simplified model of reality. The two-dimensional square-lattice Ising model is one of the simplest statistical models to show a phase transition.

In mathematics and theoretical physics, the term quantum group denotes one of a few different kinds of noncommutative algebras with additional structure. These include Drinfeld–Jimbo type quantum groups, compact matrix quantum groups, and bicrossproduct quantum groups. Despite their name, they do not themselves have a natural group structure, though they are in some sense 'close' to a group.

In Bayesian probability theory, if the posterior distribution $is in the same probability distribution family as the prior probability distribution, the prior and posterior are then called conjugate distributions, and the prior is called a conjugate prior for the likelihood function .$

In statistical mechanics and mathematics, the Bethe lattice is an infinite connected cycle-free graph where all vertices have the same number of neighbors. The Bethe lattice was introduced into the physics literature by Hans Bethe in 1935. In such a graph, each node is connected to z neighbors; the number z is called either the coordination number or the degree, depending on the field.

Critical exponents describe the behavior of physical quantities near continuous phase transitions. It is believed, though not proven, that they are universal, i.e. they do not depend on the details of the physical system, but only on some of its general features. For instance, for ferromagnetic systems, the critical exponents depend only on:

In mathematics, the Gibbs measure, named after Josiah Willard Gibbs, is a probability measure frequently seen in many problems of probability theory and statistical mechanics. It is a generalization of the canonical ensemble to infinite systems. The canonical ensemble gives the probability of the system X being in state x as

A phase-type distribution is a probability distribution constructed by a convolution or mixture of exponential distributions. It results from a system of one or more inter-related Poisson processes occurring in sequence, or phases. The sequence in which each of the phases occurs may itself be a stochastic process. The distribution can be represented by a random variable describing the time until absorption of a Markov process with one absorbing state. Each of the states of the Markov process represents one of the phases.

The quantum Heisenberg model, developed by Werner Heisenberg, is a statistical mechanical model used in the study of critical points and phase transitions of magnetic systems, in which the spins of the magnetic systems are treated quantum mechanically. It is related to the prototypical Ising model, where at each site of a lattice, a spin $represents a microscopic magnetic dipole to which the magnetic moment is either up or down. Except the coupling between magnetic dipole moments, there is also a multipolar version of Heisenberg model called the multipolar exchange interaction.$

In statistical mechanics, the two-dimensional square lattice Ising model is a simple lattice model of interacting magnetic spins. The model is notable for having nontrivial interactions, yet having an analytical solution. The model was solved by Lars Onsager for the special case that the external magnetic field H = 0. An analytical solution for the general case for $has yet to be found.$

An important question in statistical mechanics is the dependence of model behaviour on the dimension of the system. The shortcut model was introduced in the course of studying this dependence. The model interpolates between discrete regular lattices of integer dimension.

In statistical mechanics, the eight-vertex model is a generalisation of the ice-type (six-vertex) models; it was discussed by Sutherland, and Fan & Wu, and solved by Baxter in the zero-field case.

In probability theory and statistics, the Poisson distribution is a discrete probability distribution that expresses the probability of a given number of events occurring in a fixed interval of time or space if these events occur with a known constant mean rate and independently of the time since the last event. It is named after French mathematician Siméon Denis Poisson. The Poisson distribution can also be used for the number of events in other specified interval types such as distance, area, or volume. It plays an important role for discrete-stable distributions.

In computational complexity theory, QMA, which stands for Quantum Merlin Arthur, is the set of languages for which, when a string is in the language, there is a polynomial-size quantum proof that convinces a polynomial time quantum verifier of this fact with high probability. Moreover, when the string is not in the language, every polynomial-size quantum state is rejected by the verifier with high probability.

In statistical mechanics, the Griffiths inequality, sometimes also called Griffiths–Kelly–Sherman inequality or GKS inequality, named after Robert B. Griffiths, is a correlation inequality for ferromagnetic spin systems. Informally, it says that in ferromagnetic spin systems, if the 'a-priori distribution' of the spin is invariant under spin flipping, the correlation of any monomial of the spins is non-negative; and the two point correlation of two monomial of the spins is non-negative.

In probability theory, an interacting particle system (IPS) is a stochastic process $on some configuration space given by a site space, a countably-infinite-order graph and a local state space, a compact metric space . More precisely IPS are continuous-time Markov jump processes describing the collective behavior of stochastically interacting components. IPS are the continuous-time analogue of stochastic cellular automata.$

Stochastic cellular automata or probabilistic cellular automata (PCA) or random cellular automata or locally interacting Markov chains are an important extension of cellular automaton. Cellular automata are a discrete-time dynamical system of interacting entities, whose state is discrete.

Replica cluster move in condensed matter physics refers to a family of non-local cluster algorithms used to simulate spin glasses. It is an extension of the Swendsen-Wang algorithm in that it generates non-trivial spin clusters informed by the interaction states on two replicas instead of just one. It is different from the replica exchange method, as it performs a non-local update on a fraction of the sites between the two replicas at the same temperature, while parallel tempering directly exchanges all the spins between two replicas at different temperature. However, the two are often used alongside to achieve state-of-the-art efficiency in simulating spin-glass models.

In computational and mathematical biology, a biological lattice-gas cellular automaton (BIO-LGCA) is a discrete model for moving and interacting biological agents, a type of cellular automaton. The BIO-LGCA is based on the lattice-gas cellular automaton (LGCA) model used in fluid dynamics. A BIO-LGCA model describes cells and other motile biological agents as point particles moving on a discrete lattice, thereby interacting with nearby particles. Contrary to classic cellular automaton models, particles in BIO-LGCA are defined by their position and velocity. This allows to model and analyze active fluids and collective migration mediated primarily through changes in momentum, rather than density. BIO-LGCA applications include cancer invasion and cancer progression.

References

1 2 3 4 5 6 7 8 9 10 11 Ayyer, Arvind (August 2015). "A finite variant of the Toom Model". Journal of Physics: Conference Series. 638 (1): 012005. arXiv: 1503.00086 . doi: 10.1088/1742-6596/638/1/012005 . ISSN 1742-6596.
1 2 Toom, Andrei (1980). "Stable and attractive trajectories in multicomponent systems". Multicomponent Random Systems: 549–575.
↑ Bernd Gartner, Ahad N. Zehmakan (2017). "Color War: Cellular Automata with Majority Rule". Lata2017: 393–404.
1 2 Grinstein, G. (1 January 2004). "Can complex structures be generically stable in a noisy world?". IBM Journal of Research and Development. 48 (1): 5–12. doi:10.1147/rd.481.0005.
1 2 Gacs, Peter. ""A New Version of Toom's Proof", Technical Report BUCS-1995-009, Computer Science Department, Boston University, March 27, 1995". Boston University. Retrieved 8 April 2020.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[:0-1] 1 2 3 4 5 6 7 8 9 10 11 Ayyer, Arvind (August 2015). "A finite variant of the Toom Model". Journal of Physics: Conference Series. 638 (1): 012005. arXiv: 1503.00086 . doi: 10.1088/1742-6596/638/1/012005 . ISSN 1742-6596.

[:2-2] 1 2 Toom, Andrei (1980). "Stable and attractive trajectories in multicomponent systems". Multicomponent Random Systems: 549–575.

[3] Bernd Gartner, Ahad N. Zehmakan (2017). "Color War: Cellular Automata with Majority Rule". Lata2017: 393–404.

[Grinstein-4] 1 2 Grinstein, G. (1 January 2004). "Can complex structures be generically stable in a noisy world?". IBM Journal of Research and Development. 48 (1): 5–12. doi:10.1147/rd.481.0005.

[:1-5] 1 2 Gacs, Peter. ""A New Version of Toom's Proof", Technical Report BUCS-1995-009, Computer Science Department, Boston University, March 27, 1995". Boston University. Retrieved 8 April 2020.

[1]

[2]

[3]

[4]

[5]