Autómata celular utilizado para modelar la construcción universal
Una configuración sencilla en el autómata celular de von Neumann. Una señal binaria pasa repetidamente por el bucle de cable azul, utilizando estados de transmisión ordinarios excitados y quietos . Una célula 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 célula al final. Esta señal particular (1011) codifica un estado de transmisión especial dirigido al este, extendiendo así el cable rojo una célula cada vez. Durante la construcción, la nueva célula pasa por varios estados sensibilizados, dirigidos por la secuencia binaria.
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.
Definición
Configuración
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.
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 (rojo, verde, azul). Son
un estado fundamental U (48, 48, 48)
los estados de transición o sensibilizados (en 8 subestados)
S (recién sensibilizado) (255, 0, 0)
S 0 – (sensibilizado, al no haber recibido ninguna entrada durante un ciclo) (255, 125, 0)
S 00 – (sensibilizado, al no haber recibido ninguna entrada durante dos ciclos) (255, 175, 50)
S 000 – (sensibilizado, al no haber recibido ninguna entrada durante tres ciclos) (251, 255, 0)
S 01 – (sensibilizado, al no haber recibido ninguna entrada durante un ciclo y luego una entrada durante un ciclo) (255, 200, 75)
S 1 – (sensibilizado, habiendo recibido una entrada para un ciclo) (255, 150, 25)
S 10 – (sensibilizado, habiendo recibido una entrada durante un ciclo y luego ninguna entrada durante un ciclo) (255, 255, 100)
S 11 – (sensibilizado, habiendo recibido entrada durante dos ciclos) (255, 250, 125)
los estados confluentes (en 4 estados de excitación)
C 00 – inactivo (y también estará inactivo en el próximo ciclo) (0, 255, 128)
C 01 – siguiente excitado (ahora inactivo, pero se excitará en el próximo ciclo) (33, 215, 215)
C 10 – emocionado (pero estará inactivo en el próximo ciclo) (255, 255, 128)
C 11 – emocionado siguiente-emocionado (actualmente emocionado y estará emocionado en el próximo ciclo) (255, 128, 64)
los estados de transmisión ordinarios (en 4 direcciones, excitado o inactivo, lo que da lugar a 8 estados)
Dirigido al norte (excitado y tranquilo) (36, 200, 36) (106, 106, 255)
Dirigido al sur (excitado y tranquilo) (106, 255, 106) (139, 139, 255)
Dirigido al oeste (emocionado y tranquilo) (73, 255, 73) (122, 122, 255)
Dirigido al este (emocionado y tranquilo) (27, 176, 27) (89, 89, 255)
los estados especiales de transmisión (en 4 direcciones, excitado o quieto, formando 8 estados)
Dirigido al norte (excitado y tranquilo) (191, 73, 255) (255, 56, 56)
Dirigido al sur (excitado y tranquilo) (203, 106, 255) (255, 89, 89)
Dirigido al oeste (emocionado y tranquilo) (197, 89, 255) (255, 73, 73)
Dirigido al este (emocionado y tranquilo) (185, 56, 255) (235, 36, 36)
Los estados "excitados" transportan datos, a una velocidad 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 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 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.
Normas 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 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 .
Normas de construcción
Los nueve tipos de celdas que se pueden construir en el autómata de von Neumann. Aquí, las señales binarias pasan por nueve líneas de transmisión ordinarias y construyen 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 utiliza en el autómata que se muestra 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 empaquetamiento compacto de componentes.
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 0 , sin ninguna entrada, pasará al estado S 00 (100)
Una celda en el estado S 00 , sin ninguna entrada, pasará al estado S 000 (1000)
Una celda en el estado S 000 , sin ninguna entrada, pasará al estado de transmisión ordinaria dirigido al este (10000)
Una celda en el estado S 000 , dada una entrada, pasará al estado de transmisión ordinaria dirigida al norte (10001)
Una celda en el estado S 00 , dada una entrada, pasará al estado de transmisión ordinaria dirigida al oeste (1001)
Una celda en el estado S 0 , dada una entrada, pasará al estado S 01 (101)
Una celda en el estado S 01 , sin ninguna entrada, pasará al estado de transmisión ordinaria dirigida al sur (1010)
Una celda en el estado S 01 , 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 1 , sin ninguna entrada, pasará al estado S 10 (110)
Una celda en el estado S 10 , sin ninguna entrada, pasará al estado de transmisión especial dirigido al norte (1100)
Una célula en el estado S 10 , dada una entrada, pasará al estado de transmisión especial dirigido al oeste (1101)
Una célula en el estado S 1 , dada una entrada, pasará al estado S 11 (111)
Una célula en el estado S 11 , sin ninguna entrada, pasará al estado de transmisión especial dirigido al sur (1110)
Una célula en el estado S 11 , dada una entrada, pasará al estado confluente quiescente C 00 (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.
Reglas de destrucción
Aproximadamente 4000 bits de datos en una "cinta" enrollada que construye un patrón complejo. Para ello se utiliza una variante de 32 estados de los autómatas celulares de von Neumann conocida como Hutton32.
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.
