Toom's rule is a 2-dimensional cellular automaton model created by Andrei Toom in 1978. This model is both more robust and simpler than the 2-dimensional majority vote rule. 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 the bits are initialized to some value. At each discrete time step 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 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:
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 and the other with all spins in the lattice having -1. 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 the Ising model is no longer a reliable memory since there is only one ground state. The 2-dimensional majority vote cellular automaton 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=/ 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.
