Toom's rule

Toom's rule is a 2-dimensional cellular automata model created by Andrei Toom in 1978 (see ^[1] for an English translation). This model is both more robust and simpler than the 2-dimensional majority vote rule.

Neighborhood of Toom's cellular automata.

Toom's rule is a cellular automata 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 simply 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 has the spin +1 in the next time step. Toom's rule is sometimes called the NEC rule since it involves the North, East, and Center sites. If this sum is less than 0, then the current spin has spin -1 in the next time step. As there are 3 spins the sum can never equal 0.

Toom's rule, however, is a probabilistic rule and can be stated as:
(1) Apply the deterministic version of Toom's rule.

If (1) results in a spin of +1 change it to -1 with probability q.

or

If (1) results in a spin of -1 change it to +1 with probability p.^[2]

Toom's rule is a case of probabilistic cellular automata (see the article Stochastic cellular automaton).

Toom's rule as a memory

Neighborhood of the 2D Ising cellular automata.

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 we say this memory is robust in the presence of thermal noise. If however there is a local magnetic field which favors one ground state over the other, then this 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 provided that h=0. Notice that h=0 when p=q. In other words the errors are unbiased. For even small values of h this CA fails to preserve the information.

Surprisingly, Toom's rule can reliably store information in the presence of small T and h.^[2]

References

1. Toom, Andrei (1980). "Stable and attractive trajectories in multicomponent systems". Multicomponent Random Systems: 549–575.
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.