Overview
Toom's rule is a 2-dimensional cellular automaton model created by Andrei Toom in 1978. 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. The model also has a noise-dependent phase transition.
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. 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 .
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. 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. This is proven in Toom's original paper. 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. When studying the steady state where \lambda_+=\lambda_-=\alpha , the density of site n (the expected value of site n) follows the scale law: \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.
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 \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.
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. Toom's model can be applied to fault-tolerant computation.