Autómata celular von Neumann

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 cercano y colega 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, aumentado con la capacidad de que las células confluentes crucen señales y almacenen 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 más, que permite un bucle de datos, análogo al de Langton. bucles, para replicar.

Definición

Configuración

En general, los autómatas celulares (CA) constituyen una disposición de autómatas de estado finito (FSA) que se encuentran en relaciones posicionales entre sí, cada FSA intercambia información con aquellos otros FSA a los que está 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 y 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 el barrio de von Neumann.

El conjunto de FSA define un espacio de celda 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.

El Barrio (una función de agrupación) es parte de la función estatal-transición, y define para cualquier célula el conjunto de otras células sobre las cuales depende el estado de esa célula.

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

Estados

Cada FSA del espacio de celdas 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). Ellos son

1. a tierra estado U (48, 48, 48)
2. el transición o sensitis estados (en 8 subestatales)
   1. S (nuevamente sensibilizada) (255, 0, 0)
   2. S₀ – (sensibilizado, no habiendo recibido ninguna entrada para un ciclo) (255, 125, 0)
   3. S₀₀ – (sensibilizado, no habiendo recibido ninguna entrada para dos ciclos) (255, 175, 50)
   4. S₀₀₀ – (sensibilizado, habiendo recibido ninguna entrada para tres ciclos) (251, 255, 0)
   5. S₀₁ – (sensibilizado, no habiendo recibido ninguna entrada para un ciclo y luego una entrada para 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 para un ciclo y luego ninguna entrada para un ciclo) (255, 255, 100)
   8. S₁₁ – (sensibilizado, habiendo recibido entrada para dos ciclos) (255, 250, 125)
3. el confluentes estados (en 4 estados de excitación)
   1. C₀₀ – quiescente (y también será quiescente el próximo ciclo) (0, 255, 128)
   2. C₀₁ – siguiente-excitado (ahora quiescente, pero se emocionará el próximo ciclo) (33, 215, 215)
   3. C₁₀ – emocionado (pero será quiescente el próximo ciclo) (255, 255, 128)
   4. C₁₁ – emocionado siguiente-excitado (actualmente excitado y se emocionará el próximo ciclo) (255, 128, 64)
4. el transmisión ordinaria estados (en 4 direcciones, excitados o quiescentes, haciendo 8 estados)
   1. North-directed (excited and quiescent) (36, 200, 36) (106, 106, 255)
   2. Surdirigido (excitado y quiescente) (106, 255, 106) (139, 139, 255)
   3. Dirección occidental (excitada y quiescente) (73, 255, 73) (122, 122, 255)
   4. Dirección oriental (excitada y quiescente) (27, 176, 27) (89, 89, 255)
5. el transmisión especial estados (en 4 direcciones, excitados o quiescentes, haciendo 8 estados)
   1. North-directed (excited and quiescent) (191, 73, 255) (255, 56, 56)
   2. Surdirigido (excitado y quiescente) (203, 106, 255) (255, 89, 89)
   3. Dirección occidental (excitada y quiescente) (197, 89, 255) (255, 73, 73)
   4. Dirección oriental (excitada y quiescente) (185, 56, 255) (235, 36, 36)

"Emocionado" Los estados 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.

Reglas de estado de transmisión

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 al operador OR a las entradas, lo que significa que una célula en un estado de transmisión (ordinario o especial) se emocionará a la vez t+1 si cualquiera de las entradas que apuntan a ella es excitado a tiempo t
• Los datos pasan de la célula A en un estado de transmisión ordinario a una célula adyacente B en un estado de transmisión ordinario, según la propiedad de dirección A (Independientemente) B también se dirige hacia A, en cuyo caso los datos desaparecen).
• Los datos pasan de la célula A en un estado de transmisión especial a una célula adyacente B en un estado de transmisión especial, según las mismas reglas que para los estados de transmisión ordinario.
• Los dos subconjuntos de estados de transmisión, ordinarios y especiales, son mutuamente antagónicos:
  • Dada una celda A a la vez t en el estado de transmisión ordinario excitado
  • apuntando a una célula B en cualquier estado de transmisión especial
  • a la vez t+1 célula B se convertirá en el estado del suelo. 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 "punto" a una célula en el estado de transmisión ordinario

Reglas estatales confluentes

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

• Los estados confluentes no pasan datos entre sí.
• Los estados confluentes toman insumos de uno o más estados de transmisión ordinarios, y entregan salida a 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 estatal de transmisión.
• Los datos mantenidos por un estado confluente se pierden si ese estado no tiene un estado de transmisión adyacente que tampoco se señala en el estado confluente.
• Así, las células del estado confluente se utilizan como "puentes" de las líneas de transmisión de las células estatales ordinarias a las especiales de transmisión.
• El estado confluente aplica al operador AND a las entradas, sólo "salvando" una entrada excitada si todas las entradas potenciales se excitan simultáneamente.
• Las células confluentes retrasan las señales de una generación más que las células OTS; esto es necesario debido a limitaciones de paridad.

Reglas de construcción

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 recibe 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 "descansar" finalmente. en un estado de transmisión quiescente o confluente.

La elección del estado de destino que alcanzará 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 va desde el estado fundamental a cada uno de los estados de transmisión quiescente y confluente.

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

• a cell in the ground state U, dado un aporte, se transición a S (nuevamente sensibilizado) estado en el próximo ciclo (1)
• a cell in the S estado, dado que no hay entrada, pasará a S₀ Estado (10)
  • a cell in the S₀ estado, dado que no hay entrada, pasará a S₀₀ Estado (100)
    • a cell in the S₀₀ estado, dado que no hay entrada, pasará a S₀₀₀ Estado (1000)
      • a cell in the S₀₀₀ estado, dado no entrada, pasará al estado de transmisión ordinario dirigido por el este (10000)
      • a cell in the S₀₀₀ estado, dada una entrada, se pasará al estado de transmisión ordinario dirigido al norte (10001)
    • a cell in the S₀₀ estado, dada una entrada, pasará al estado de transmisión ordinario dirigido por el oeste (1001)
  • a cell in the S₀ estado, dado un aporte, se transición a S₀₁ Estado (101)
    • a cell in the S₀₁ estado, dado que no hay entrada, pasará al estado de transmisión ordinario dirigido por el sur (1010)
    • a cell in the S₀₁ estado, dada una entrada, pasará al estado de transmisión especial dirigido por el este (1011)
• a cell in the S estado, dado un aporte, se transición a S₁ Estado (11)
  • a cell in the S₁ estado, dado que no hay entrada, pasará a S₁₀ Estado (110)
    • a cell in the S₁₀ estado, dado que no hay entrada, pasará al estado de transmisión especial dirigido por el norte (1100)
    • a cell in the S₁₀ estado, dada una entrada, pasará al estado de transmisión especial dirigido por el oeste (1101)
  • a cell in the S₁ estado, dado un aporte, se transición a S₁₁ estado (111)
    • a cell in the S₁₁ estado, dado no entrada, pasará al estado de transmisión especial dirigido por el sur (1110)
    • a cell in the S₁₁ estado, dado un aporte, se transición hacia el estado confluente quiescente C₀₀ (1111)

Note that:

• un ciclo más de entrada (cuatro después de la sensibilización inicial) se requiere para construir el estado de transmisión ordinario 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 quiescente "default" que resulta en la construcción es el estado de transmisión ordinario dirigido hacia el este - que requiere una entrada inicial de sensibilización, y luego cuatro ciclos de ninguna entrada.

Reglas de destrucción

• Una entrada en una célula confluente-estatal de una célula estatal especial-transmisión dará lugar a que la célula estatal confluente se reduzca de nuevo al estado del suelo.
• Asimismo, una entrada en una célula estatal de transmisión ordinaria de una célula estatal de transmisión especial dará lugar a que la célula estatal de transmisión ordinaria se reduzca al estado del suelo.
• Por el contrario, una entrada en una célula estatal de transmisión especial de una célula estatal de transmisión ordinaria dará lugar a que la célula estatal de transmisión especial se reduzca al estado del suelo.