Autómata celular Von Neumann

Autómata celular utilizado para modelar la construcción universal

Una configuración simple en el autómata celular de von Neumann. Una señal binaria se pasa repetidamente alrededor del circuito de cable azul, utilizando estados de transmisión ordinarios excitados e inactivos . Una celda confluente duplica la señal en un tramo de cable rojo que consta de estados de transmisión especiales . La señal pasa por este cable y construye una nueva celda al final. Esta señal particular (1011) codifica un estado de transmisión especial dirigido al este, extendiendo así el cable rojo en una celda cada vez. Durante la construcción, la nueva celda pasa por varios estados sensibilizados, dirigidos por la secuencia binaria.

Los autómatas celulares de Von Neumann son la expresión original de los autómatas celulares , cuyo desarrollo fue impulsado por sugerencias hechas a John von Neumann por 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 la máquina , 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 las células confluentes para 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.

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 las otras FSA a las que es posicionalmente adyacente. En el autómata celular de von Neumann, las máquinas (o células ) de estados finitos 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 conoce como la vecindad 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.

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 hacen sus transiciones de forma sincrónica, al paso de un "reloj" universal como en un circuito digital sincrónico.

Estados

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 en (rojo, verde, azul). Ellos 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, sin 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, sin 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 para un ciclo y luego ninguna entrada para 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 estará excitado en el próximo ciclo)  (33, 215, 215)
   3. C ₁₀ - excitado (pero estará inactivo en el próximo ciclo)  (255, 255, 128)
   4. C ₁₁ - emocionado próximo emocionado (actualmente emocionado y estará emocionado el próximo ciclo)  (255, 128, 64)
4. los estados de transmisión ordinarios (en 4 direcciones, excitado o inactivo, formando 8 estados)
   1. Dirigido al norte (emocionado y en reposo)   (36, 200, 36)   (106, 106, 255)
   2. Dirigido al sur (emocionado y en reposo)   (106, 255, 106)   (139, 139, 255)
   3. Dirigido al oeste (emocionado y en reposo)   (73, 255, 73)   (122, 122, 255)
   4. Dirigido al este (emocionado y en reposo)   (27, 176, 27)   (89, 89, 255)
5. los estados de transmisión especiales (en 4 direcciones, excitado o inactivo, haciendo 8 estados)
   1. Dirigido al norte (emocionado y en reposo)   (191, 73, 255)   (255, 56, 56)
   2. Dirigido al sur (emocionado y en reposo)   (203, 106, 255)   (255, 89, 89)
   3. Dirigido al oeste (emocionado y en reposo)   (197, 89, 255)   (255, 73, 73)
   4. Dirigido al este (emocionado y en reposo)   (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 retardo de un ciclo, por lo que efectivamente retienen dos bits de datos en un momento dado.

Reglas del 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 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 pasan de la celda A en un estado de transmisión ordinario a una celda B adyacente en un estado de transmisión ordinario, de acuerdo con la propiedad de dirección de A (a menos que B también se dirija 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 tiempo 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 celda B se convertirá en el 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 "apuntando" a una celda en el estado de transmisión ordinario

Reglas estatales confluentes

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

• Los estados confluentes no se transmiten 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 retenidos por un estado confluente se pierden si ese estado no tiene un estado de transmisión adyacente que tampoco apunte al estado confluente.
• Por tanto, las células de estado confluente se utilizan como "puentes" desde las líneas de transmisión de células de estado de transmisión ordinarias a especiales.
• El estado confluente aplica el operador AND a las entradas, solo "guardando" una entrada excitada 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 .

Reglas de construcción

Los nueve tipos de células que se pueden construir en el CA de von Neumann. Aquí, las señales binarias pasan a lo largo de nueve líneas de transmisión ordinarias, construyendo una nueva celda cuando encuentran un estado fundamental al final. Por ejemplo, la cadena binaria 1011 se muestra en la quinta línea y construye el estado de transmisión especial dirigido al este; este es el mismo proceso que se usa en el autómata en la parte superior de esta página. Tenga en cuenta que no hay interacción entre cables vecinos, a diferencia de Wireworld, por ejemplo, lo que permite un embalaje compacto de componentes.

Inicialmente, la mayor parte de la célula-espacio, el universo del autómata celular, es "en blanco", que consiste en células en el estado fundamental U . Cuando se le da una excitación de entrada desde un estado de transmisión ordinario o especial vecino, la celda en el estado fundamental se "sensibiliza", pasando por una serie de estados antes de finalmente "descansar" en un estado de transmisión inactivo o confluente.

La elección del estado de destino que alcanzará la celda está determinada por la secuencia de señales de entrada. Por lo tanto, los estados de transición / sensibilizados 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 inactiva y confluente.

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

• una celda en el estado fundamental U , dada una entrada, pasará al estado S (recién sensibilizada) en el siguiente ciclo (1)
• una celda en el estado S , sin entrada, pasará al estado S ₀ (10)
  • una celda en el estado S ₀ , sin entrada, pasará al estado S ₀₀ (100)
    • una celda en el estado S ₀₀ , sin entrada, pasará al estado S ₀₀₀ (1000)
      • una celda en el estado S ₀₀₀ , sin entrada, pasará al estado de transmisión ordinaria dirigida 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 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 dirigida al este (1011)
• una celda en el estado S , dada una entrada, pasará al estado S ₁ (11)
  • una celda en el estado S ₁ , sin entrada, pasará al estado S ₁₀ (110)
    • una celda en el estado S ₁₀ , sin entrada, pasará al estado de transmisión especial dirigida al norte (1100)
    • una celda en el estado S ₁₀ , dada una entrada, pasará al estado de transmisión especial dirigida al oeste (1101)
  • una celda en el estado S ₁ , dada una entrada, pasará al estado S ₁₁ (111)
    • una celda en el estado S ₁₁ , sin entrada, pasará al estado de transmisión especial dirigida al sur (1110)
    • una celda en el estado S ₁₁ , dada una entrada, pasará al estado confluente inactivo 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 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 inactivo "predeterminado" que da como resultado 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.

Reglas de destrucción

Aproximadamente 4000 bits de datos en una "cinta" enrollada construyendo un patrón complejo. Esto utiliza una variación de 32 estados de los autómatas celulares de von Neumann conocida como Hutton32.

• Una entrada en una celda de estado confluente desde una celda de estado de transmisión especial dará como resultado que la celda de estado confluente se reduzca de nuevo al estado fundamental.
• Asimismo, una entrada en 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 se reduzca de nuevo al estado fundamental.
• A la inversa, una entrada en 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.

Ver también

• Autómata celular de codd
• Bucles de Langton
• Constructor universal de von Neumann
• Wireworld

Referencias

• Von Neumann, J. y AW Burks (1966). Teoría de los autómatas que se reproducen a sí mismos. Urbana, Prensa de la Universidad de Illinois. [1]

Enlaces externos

• Golly : admite CA de von Neumann junto con Game of Life y otros conjuntos de reglas.