Autómata celular von Neumann

En general, los autómatas celulares (AC) constituyen una disposición de autómatas de estados finitos (AEF) que mantienen relaciones posicionales entre sí, intercambiando información entre sí los AEF adyacentes. En el autómata celular de von Neumann, las máquinas de estados finitos (o celdas ) se organizan en una cuadrícula cartesiana bidimensional e interactúan con las cuatro celdas circundantes. Dado que el autómata celular de von Neumann fue el primer ejemplo en utilizar esta disposición, se le conoce como la vecindad de von Neumann .

El conjunto de autómatas finitos define un espacio de celdas de tamaño infinito. Todos los autómatas finitos son idénticos en términos de función de transición de estado o conjunto de reglas.

La vecindad (una función de agrupación) forma parte de la función de transición de estado y define, para cualquier célula, el conjunto de otras células de las que depende el estado de esa célula.

Todas las células realizan sus transiciones de forma síncrona, al ritmo de un "reloj" universal, como en un circuito digital síncrono.

Cada autómata finito de estados (AFE) del espacio celular de von Neumann puede aceptar cualquiera de los 29 estados del conjunto de reglas. El conjunto de reglas se agrupa en cinco subconjuntos ortogonales. Cada estado incluye el color de la celda en el programa de autómatas celulares Golly (rojo, verde, azul). Son

1. un estado fundamental U (48, 48, 48)  
2. los estados de transición o sensibilizados (en 8 subestados)
   1. S (recién sensibilizado) (255, 0, 0)  
   2. S ₀ – (sensibilizado, sin haber recibido ninguna entrada durante un ciclo) (255, 125, 0)  
   3. S ₀₀ – (sensibilizado, al no haber recibido ninguna entrada durante dos ciclos) (255, 175, 50)  
   4. S ₀₀₀ – (sensibilizado, sin haber recibido ninguna entrada durante tres ciclos) (251, 255, 0)  
   5. S ₀₁ – (sensibilizado, habiendo no recibido ninguna entrada durante un ciclo y luego una entrada durante un ciclo) (255, 200, 75)  
   6. S ₁ – (sensibilizado, habiendo recibido una entrada durante un ciclo) (255, 150, 25)  
   7. S ₁₀ – (sensibilizado, habiendo recibido una entrada durante un ciclo y luego ninguna entrada durante un ciclo) (255, 255, 100)  
   8. S ₁₁ – (sensibilizado, habiendo recibido entrada durante dos ciclos) (255, 250, 125)  
3. los estados confluentes (en 4 estados de excitación)
   1. C ₀₀ – inactivo (y también estará inactivo en el próximo ciclo) (0, 255, 128)  
   2. C ₀₁ – siguiente excitado (ahora en reposo, pero se excitará en el próximo ciclo) (33, 215, 215)  
   3. C ₁₀ – excitado (pero estará inactivo el próximo ciclo) (255, 255, 128)  
   4. C ₁₁ – excitado siguiente-excitado (actualmente excitado y se excitará en el próximo ciclo) (255, 128, 64)  
4. los estados de transmisión ordinarios (en 4 direcciones, excitados o en reposo, lo que da un total de 8 estados)
   1. Orientado al norte (excitado y en reposo) (36, 200, 36) (106, 106, 255)    
   2. Orientado al sur (excitado y en reposo) (106, 255, 106) (139, 139, 255)    
   3. Orientado hacia el oeste (excitado y quieto) (73, 255, 73) (122, 122, 255)    
   4. Dirigido hacia el este (excitado y quieto) (27, 176, 27) (89, 89, 255)    
5. los estados de transmisión especiales (en 4 direcciones, excitados o en reposo, lo que da como resultado 8 estados)
   1. Orientado al norte (excitado y en reposo) (191, 73, 255) (255, 56, 56)    
   2. Orientado al sur (excitado y en reposo) (203, 106, 255) (255, 89, 89)    
   3. Orientado hacia el oeste (excitado y quieto) (197, 89, 255) (255, 73, 73)    
   4. Orientado hacia el este (excitado y quieto) (185, 56, 255) (235, 36, 36)    

Los estados "excitados" transportan datos a una velocidad de un bit por cada paso de transición de estado.

Cabe destacar que los estados confluentes tienen la propiedad de un retardo de un ciclo, lo que permite mantener efectivamente dos bits de datos en cualquier momento dado.

El flujo de bits entre celdas se indica mediante la propiedad de dirección. Se aplican las siguientes reglas:

• Los estados de transmisión aplican el operador OR a las entradas, lo que significa que una celda en un estado de transmisión (ordinario o especial) se excitará en el tiempo t+1 si alguna de las entradas que apuntan a ella se excita en el tiempo t.
• Los datos se transmiten desde la celda A en un estado de transmisión normal a una celda adyacente B en un estado de transmisión normal, según la propiedad de dirección de A (a menos que B también esté dirigida hacia A , en cuyo caso los datos desaparecen).
• Los datos se transmiten de la celda A, que se encuentra en un estado de transmisión especial, a una celda B adyacente , también en un estado de transmisión especial, siguiendo las mismas reglas que para los estados de transmisión ordinarios.
• Los dos subconjuntos de estados de transmisión, ordinarios y especiales, son mutuamente antagónicos:
  • Dada una celda A en el instante t en el estado de transmisión ordinaria excitada
  • apuntando a una celda B en cualquier estado de transmisión especial
  • En el instante t+1, la celda B pasará al estado fundamental. La celda de transmisión especial ha sido "destruida".
  • Una secuencia similar ocurrirá en el caso de una celda en el estado de transmisión especial que "apunta" a una celda en el estado de transmisión ordinario.

Las siguientes reglas específicas se aplican a los estados confluentes:

• Los estados confluentes no se transmiten datos entre sí.
• Los estados confluentes toman como entrada uno o más estados de transmisión ordinarios y entregan como salida estados de transmisión, ordinarios y especiales, que no están dirigidos hacia el estado confluente.
• Los datos no se transmiten en contra de la propiedad de dirección del estado de transmisión.
• Los datos que contiene un estado confluente se pierden si ese estado no tiene un estado de transmisión adyacente que tampoco apunte al estado confluente.
• De este modo, las células en estado confluente se utilizan como "puentes" entre las líneas de transmisión de las células en estado de transmisión ordinario y las células en estado de transmisión especial.
• El estado confluente aplica el operador AND a las entradas, "guardando" una entrada excitada solo si todas las entradas potenciales se excitan simultáneamente.
• Las células confluentes retrasan las señales una generación más que las células OTS; esto es necesario debido a las restricciones de paridad .

Inicialmente, gran parte del espacio celular, el universo del autómata celular, está "vacío", compuesto por células en el estado fundamental U. Al recibir una excitación de entrada de un estado de transmisión ordinario o especial vecino, la célula en el estado fundamental se "sensibiliza", pasando por una serie de estados antes de finalmente "descansar" en un estado de transmisión quiescente o confluente.

La elección del estado final que alcanzará la célula viene determinada por la secuencia de señales de entrada. Por lo tanto, los estados de transición/sensibilización pueden considerarse como los nodos de un árbol de bifurcación que va desde el estado fundamental hasta cada uno de los estados de transmisión en reposo y confluencia.

En el siguiente árbol, la secuencia de entradas se muestra como una cadena binaria después de cada paso:

• Una célula en el estado fundamental U , dada una entrada, pasará al estado S (recién sensibilizado) en el siguiente ciclo (1).
• Una célula en estado S , sin recibir ninguna entrada, pasará al estado S ₀ (10)
  • Una célula en el estado S ₀ , sin recibir ninguna entrada, pasará al estado S ₀₀ (100).
    • Una célula en el estado S ₀₀ , sin recibir ninguna entrada, pasará al estado S ₀₀₀ (1000).
      • Una celda en el estado S ₀₀₀ , sin ninguna entrada, pasará al estado de transmisión ordinaria dirigida hacia el este (10000).
      • Una celda en el estado S ₀₀₀ , dada una entrada, pasará al estado de transmisión ordinaria dirigida hacia el norte (10001).
    • Una celda en el estado S ₀₀ , dada una entrada, pasará al estado de transmisión ordinaria dirigida hacia el oeste (1001).
  • Una célula en el estado S ₀ , dada una entrada, pasará al estado S ₀₁ (101).
    • Una celda en el estado S ₀₁ , sin ninguna entrada, pasará al estado de transmisión ordinaria dirigida hacia el sur (1010).
    • Una celda en el estado S ₀₁ , dada una entrada, pasará al estado de transmisión especial dirigido hacia el este (1011).
• Una célula en el estado S , dada una entrada, pasará al estado S ₁ (11)
  • Una célula en el estado S ₁ , sin recibir ninguna entrada, pasará al estado S ₁₀ (110).
    • Una célula en el estado S ₁₀ , sin recibir ninguna entrada, pasará al estado de transmisión especial dirigido hacia el norte (1100).
    • Una célula en el estado S ₁₀ , dada una entrada, pasará al estado de transmisión especial dirigido hacia el oeste (1101).
  • Una célula en el estado S ₁ , dada una entrada, pasará al estado S ₁₁ (111).
    • Una célula en el estado S ₁₁ , sin recibir ninguna entrada, pasará al estado de transmisión especial dirigido hacia el sur (1110).
    • Una célula en el estado S ₁₁ , dada una entrada, pasará al estado confluente quiescente C ₀₀ (1111).

Tenga en cuenta que:

• Se requiere un ciclo más de entrada (cuatro después de la sensibilización inicial) para construir el estado de transmisión ordinaria dirigida hacia el este o el norte que cualquiera de los otros estados (que requieren tres ciclos de entrada después de la sensibilización inicial),
• El estado de reposo "predeterminado" que da lugar a la construcción es el estado de transmisión ordinaria dirigida hacia el este, que requiere una entrada de sensibilización inicial y, a continuación, cuatro ciclos sin entrada.

• Una entrada de datos a una celda en estado confluente desde una celda en estado de transmisión especial dará como resultado que la celda en estado confluente se reduzca de nuevo al estado fundamental.
• Del mismo modo, una entrada a una celda de estado de transmisión ordinaria desde una celda de estado de transmisión especial dará como resultado que la celda de estado de transmisión ordinaria vuelva a su estado fundamental.
• Por el contrario, una entrada a una celda de estado de transmisión especial desde una celda de estado de transmisión ordinaria dará como resultado que la celda de estado de transmisión especial se reduzca de nuevo al estado fundamental.