Autómata celular von Neumann

Los autómatas celulares de von Neumann son la expresión original de los autómatas celulares , cuyo desarrollo fue impulsado por las sugerencias que le hizo a John von Neumann su amigo íntimo y compañero matemático Stanislaw Ulam . Su propósito original era proporcionar información sobre los requisitos lógicos para la autorreplicación de las máquinas , y se utilizaron en el constructor universal de von Neumann .

El autómata celular de Nobili es una variación del autómata celular de von Neumann, ampliada con la capacidad de las células confluentes de cruzar señales y almacenar información. El primero requiere tres estados adicionales, por lo que el autómata celular de Nobili tiene 32 estados, en lugar de 29. El autómata celular de Hutton es otra variación, que permite que un bucle de datos, análogo a los bucles de Langton , se replique.

En general, los autómatas celulares (AC) constituyen una disposición de autómatas de estados finitos (AEF) que se encuentran en relaciones posicionales entre sí, cada AEF intercambiando información con aquellos otros AEF a los que se encuentra posicionalmente adyacente. En el autómata celular de von Neumann, las máquinas de estados finitos (o células ) están dispuestas en una cuadrícula cartesiana bidimensional e interactúan con las cuatro células circundantes. Como el autómata celular de von Neumann fue el primer ejemplo en utilizar esta disposición, se lo conoce como el vecindario de von Neumann .

El conjunto de FSA define un espacio de celdas de tamaño infinito. Todas las FSA son idénticas en términos de función de transición de estado o conjunto de reglas.

La vecindad (una función de agrupación) es parte de la función de transición de estado y define para cualquier celda el conjunto de otras celdas del que depende el estado de esa celda.

Todas las células realizan sus transiciones sincrónicamente, al ritmo de un "reloj" universal, como en un circuito digital sincrónico.

Cada FSA 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, al no 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, al no haber recibido ninguna entrada durante tres ciclos)  (251, 255, 0)
   5. S ₀₁ – (sensibilizado, al no haber recibido ninguna entrada durante un ciclo y luego una entrada durante un ciclo)  (255, 200, 75)
   6. S ₁ – (sensibilizado, habiendo recibido una entrada para 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 inactivo, pero se excitará en el próximo ciclo)  (33, 215, 215)
   3. C ₁₀ – emocionado (pero estará inactivo en el próximo ciclo)  (255, 255, 128)
   4. C ₁₁ – emocionado siguiente-emocionado (actualmente emocionado y estará emocionado en el próximo ciclo)  (255, 128, 64)
4. los estados de transmisión ordinarios (en 4 direcciones, excitado o inactivo, lo que da lugar a 8 estados)
   1. Dirigido al norte (excitado y tranquilo)  (36, 200, 36)   (106, 106, 255)
   2. Dirigido al sur (excitado y tranquilo)  (106, 255, 106)   (139, 139, 255)
   3. Dirigido al oeste (emocionado y tranquilo)  (73, 255, 73)   (122, 122, 255)
   4. Dirigido al este (emocionado y tranquilo)  (27, 176, 27)   (89, 89, 255)
5. los estados especiales de transmisión (en 4 direcciones, excitado o quieto, formando 8 estados)
   1. Dirigido al norte (excitado y tranquilo)  (191, 73, 255)   (255, 56, 56)
   2. Dirigido al sur (excitado y tranquilo)  (203, 106, 255)   (255, 89, 89)
   3. Dirigido al oeste (emocionado y tranquilo)  (197, 89, 255)   (255, 73, 73)
   4. Dirigido al este (emocionado y tranquilo)  (185, 56, 255)   (235, 36, 36)

Los estados "excitados" transportan datos, a razón de un bit por paso de transición de estado.

Tenga en cuenta que los estados confluentes tienen la propiedad de un retraso de un ciclo, por lo que efectivamente contienen dos bits de datos en un 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 momento t+1 si alguna de las entradas que apuntan a ella se excita en el momento t
• Los datos pasan de la celda A en un estado de transmisión ordinario a una celda adyacente B en un estado de transmisión ordinario, de acuerdo con 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 pasan de la celda A en un estado de transmisión especial a una celda B adyacente en un estado de transmisión especial, de acuerdo con las mismas reglas que para los estados de transmisión ordinarios.
• Los dos subconjuntos de estados de transmisión, ordinario y especial, son mutuamente antagónicos:
  • Dada una celda A en el momento t en el estado de transmisión ordinario excitado
  • apuntando a una celda B en cualquier estado de transmisión especial
  • En el momento t+1 la célula B pasará al estado fundamental. La célula de transmisión especial ha sido "destruida".
  • Una secuencia similar ocurrirá en el caso de una célula en el estado de transmisión especial que "apunta" a una célula en el estado de transmisión ordinario.

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

• Los estados confluentes no pasan datos entre sí.
• Los estados confluentes toman la entrada de uno o más estados de transmisión ordinarios y entregan la salida a los estados de transmisión, ordinarios y especiales, que no están dirigidos hacia el estado confluente.
• Los datos no se transmiten contra la propiedad de dirección del estado de transmisión.
• Los datos almacenados en un estado confluente se pierden si ese estado no tiene ningún estado de transmisión adyacente que tampoco apunte al estado confluente.
• De esta manera, las células en estado confluente se utilizan como "puentes" desde las líneas de transmisión de las células en estado ordinario a 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 restricciones de paridad .

Inicialmente, gran parte del espacio celular, el universo del autómata celular, está "en blanco", y consiste en células en el estado fundamental U. Cuando se le da 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 de destino al que llegará la célula está 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 conduce desde el estado fundamental a cada uno de los estados de transmisión inactiva y confluente.

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 el estado S , sin ninguna entrada, pasará al estado S0 ₍ 10)
  • Una celda en el estado S ₀ , sin ninguna entrada, pasará al estado S ₀₀ (100)
    • Una celda en el estado S ₀₀ , sin ninguna entrada, pasará al estado S ₀₀₀ (1000)
      • Una celda en el estado S ₀₀₀ , sin ninguna entrada, pasará al estado de transmisión ordinaria dirigido al este (10000)
      • Una celda en el estado S ₀₀₀ , dada una entrada, pasará al estado de transmisión ordinaria dirigida al norte (10001)
    • Una celda en el estado S ₀₀ , dada una entrada, pasará al estado de transmisión ordinaria dirigida al oeste (1001)
  • Una celda 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 al sur (1010)
    • Una celda en el estado S ₀₁ , dada una entrada, pasará al estado de transmisión especial dirigido al este (1011)
• Una célula en el estado S , dada una entrada, pasará al _estado S1 (11)
  • Una célula en el estado S ₁ , sin ninguna entrada, pasará al estado S ₁₀ (110)
    • Una celda en el estado S ₁₀ , sin ninguna entrada, pasará al estado de transmisión especial dirigido al norte (1100)
    • Una célula en el estado S ₁₀ , dada una entrada, pasará al estado de transmisión especial dirigido al 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 ninguna entrada, pasará al estado de transmisión especial dirigido al 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 dirigido al este o al 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 resulta en la construcción es el estado de transmisión ordinario dirigido al este, que requiere una entrada de sensibilización inicial y luego cuatro ciclos sin entrada.

• Una entrada 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 nuevamente al estado fundamental.
• De la misma manera, una entrada a una celda de estado de transmisión ordinario desde una celda de estado de transmisión especial dará como resultado que la celda de estado de transmisión ordinario se reduzca nuevamente al estado fundamental.
• Por el contrario, una entrada a una celda de estado de transmisión especial desde una celda de estado de transmisión ordinario dará como resultado que la celda de estado de transmisión especial se reduzca nuevamente al estado fundamental.

• El autómata celular de Codd
• Los bucles de Langton
• Constructor universal de von Neumann
• Mundo de cables

• Von Neumann, J. y AW Burks (1966). Teoría de los autómatas autorreproductores. Urbana, University of Illinois Press. [1]

• Golly: admite el CA de von Neumann junto con el Juego de la Vida y otros conjuntos de reglas.