Toom's rule

Toom's rule is a 2-dimensional cellular automaton 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 (see [2] for more details).

Neighborhood of Toom's cellular automaton.
Toom's rule animation. The black lines are domain walls between up spins and down spins.

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 (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.[3]

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

Toom's rule as a memory
Density of + for the invariant law of Toom's model. In the regime where p and q are small, there are two invariant laws.
Neighborhood of the 2D Ising cellular automaton.

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 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.[3][4]

gollark: That's nice.
gollark: That seems basically in accordance with the bodily autonomy thing.
gollark: If you're going to say "you technically can do whatever you want with your own body, but we're going to practically ban large classes of things" then that can absolutely generalize to abortion or anything else.
gollark: I assumed you meant "bodily autonomy", i.e. you own your body and get to decide what happens to it, based on you saying something about thinking the average person should support ownership of their own body.
gollark: "Ownership of your body ≠ Ownership of abortion drugs or the right to have a doctor do abortions."

References
  1. Toom, Andrei (1980). "Stable and attractive trajectories in multicomponent systems". Multicomponent Random Systems: 549–575.
  2. Bernd Gartner, Ahad N. Zehmakan (2017). "Color War:Cellular Automata with Majority Rule". Lata2017: 393–404.
  3. 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.
  4. 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 article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.