La regla de Toom es un modelo de autómata celular bidimensional creado por Andréi Toom en 1978. Es una modificación de la regla de votación mayoritaria bidimensional y puede tener una memoria más robusta cuando se considera como un sistema físico térmico en la teoría estadística de campos. El modelo también tiene una transición de fase dependiente del ruido.

Declaración

La regla de Toom es un autómata celular que actúa sobre una red cuadrada bidimensional. En cada nodo de esta red hay un espín con valor +1 o -1. En el instante , los bits se inicializan con algún valor. En cada paso de tiempo discreto , la red evoluciona según la regla de Toom. Esta regla se aplica simultáneamente en cada punto.

Una versión determinista de la regla de Toom se puede enunciar como:

En cada lugar de la red, si la suma del espín del sitio actual (central) más el espín del vecino al norte más el espín del vecino al este es mayor que 0, entonces el espín actual se convierte en +1 en el siguiente paso de tiempo.

Si esta suma es menor que 0, entonces el espín actual se convierte en -1 en el siguiente paso de tiempo. Como hay 3 espines, la suma nunca puede ser igual a 0.

La regla de Toom a veces se denomina regla NEC, ya que involucra los sitios Norte, Este y Central.

La versión general de la regla de Toom es probabilística y se puede enunciar como:

Aplicar la versión determinista de la regla de Toom. Si el paso 1 resulta en un espín de +1, cámbielo a -1 con probabilidad q. De lo contrario, si el paso 2 resulta en un espín de -1, cámbielo a +1 con probabilidad p.

La versión determinista se puede recuperar estableciendo p=q=0.

La regla de Toom es un ejemplo de autómata celular probabilístico (véase autómatas celulares estocásticos), definido en la red .

Propiedades Cuando , el sistema tenderá a favorecer un espín sobre el otro, lo que puede interpretarse como el efecto de un campo magnético.

El modelo tiene una transición de fase. Para valores de p y q suficientemente bajos, existen al menos dos estados estacionarios, pero para valores de p y q suficientemente altos, existe un único estado estacionario. Esto se demuestra en el artículo original de Toom.

Cuando p=q=0, existe un estado estacionario con una interfaz escalonada entre los espines +1 y -1. Cuando p y q son pequeños, se producen fluctuaciones en esta interfaz. Se han desarrollado modelos adicionales para estudiar la dinámica de la interfaz como una configuración de espines unidimensional (en ).

se define como la tasa (probabilidad) de que cada espín +1 intercambie su posición con el primer espín -1 a su derecha. La tasa se define de forma similar. Se puede simplificar aún más considerando que solo el espín más a la izquierda en un bloque (de espines idénticos) intercambia su posición con el primer espín opuesto a su derecha. Además, el primer espín puede invertir su posición independientemente con una probabilidad . Este modelo unidimensional también se conoce como la regla de Toom.

Al estudiar el estado estacionario donde , la densidad del sitio n (el valor esperado del sitio n) sigue la ley de escala: . También se puede definir una versión finita de esta regla de Toom unidimensional donde hay L sitios (modelo de interfaz finita). El -1 más a la izquierda en un bloque se intercambia con el primer +1 a la derecha con probabilidad , y el +1 más a la izquierda en un bloque se intercambia con el primer -1 a la derecha con probabilidad . En este modelo, hay u espines hacia arriba y d espines hacia abajo, donde u+d=L. También hay configuraciones de los L sitios.

Para esta regla de Toom finita, se pueden calcular las funciones de correlación, la función de partición y la matriz estocástica, así como sus autovalores. Se ha demostrado que cuando y n < L es grande, la función de densidad sigue la misma ley del inverso del cuadrado que la anterior: .

Cuando , se conjetura que la densidad decae como 1/n:.

La regla de Toom como memoria

La regla de Toom es una variante dinámica del modelo de Ising. Existen muchas reglas dinámicas para el modelo de Ising cuyo estado estacionario es gibbsiano.

El modelo de Ising bidimensional ferromagnético, en ausencia de campos magnéticos locales, tiene dos estados fundamentales: uno con todos los espines de la red con +1 (espín hacia arriba) y otro con todos los espines de la red con -1 (espín hacia abajo). Por esta razón, el modelo de Ising bidimensional puede considerarse una memoria que almacena un bit de información en su estado fundamental.

Esta memoria es robusta en el sentido de que, si los errores provocan que algunos espines cambien de dirección, al regresar al estado fundamental se conservará la información almacenada. Estos errores se producen debido al ruido térmico del sistema. Por lo tanto, se dice que esta memoria es robusta en presencia de ruido térmico. Sin embargo, si existe un campo magnético local que favorece un estado fundamental sobre otro, el modelo de Ising deja de ser una memoria fiable, ya que solo existe un estado fundamental.

El autómata celular (AC) bidimensional de votación mayoritaria es análogo al modelo de Ising. El AC de votación mayoritaria evoluciona cada sitio de la red tomando el valor de espín del sitio actual más el de los cuatro sitios vecinos, y asigna a este espín +1 en el siguiente paso temporal si la suma es positiva y -1 si es negativa. Al igual que con la regla de Toom, se puede construir una versión probabilística del AC de votación mayoritaria donde la salida puede cambiar con probabilidad q de espín +1 a espín -1 y con probabilidad p de espín -1 a espín +1.

En lugar de estados fundamentales, la información se almacena en estados estables del AC. Estos son estados tales que los espines en la red no cambian al ser manipulados por el AC. Es fácil demostrar que los estados con todos los espines en +1 y todos los estados en -1 son estados estables cuando q=p=0. Por lo tanto, el autómata celular de votación mayoritaria puede utilizarse para almacenar información. Se pueden definir términos análogos al ruido térmico y al campo magnético como T=p+q y h=(p-q)/(p+q), respectivamente. De forma similar al modelo de Ising, el autómata celular de votación mayoritaria puede almacenar información de forma fiable para valores pequeños de T. A diferencia del modelo de Ising, si T es suficientemente pequeño, esto se cumple incluso para valores arbitrarios de h.

El modelo de Toom puede aplicarse a la computación tolerante a fallos.

Referencias

Categoría:Autómata celular