Bloquear autómata celular

Un autómata celular de bloques o autómata celular de particionamiento es un tipo especial de autómata celular en el que la red de celdas se divide en bloques no superpuestos (con diferentes particiones en diferentes pasos de tiempo) y la regla de transición se aplica a un bloque completo a la vez en lugar de a una sola celda. Los autómatas celulares de bloques son útiles para simulaciones de cantidades físicas, porque es sencillo elegir reglas de transición que obedezcan restricciones físicas como las leyes de reversibilidad y conservación . ^[1]

Un autómata celular en bloque consta de los siguientes componentes: ^{[1] [2]}

• Una red regular de células
• Un conjunto finito de estados en los que puede encontrarse cada célula
• Una partición de las celdas en una teselación uniforme en la que cada mosaico de la partición tiene el mismo tamaño y forma.
• Una regla para cambiar la partición después de cada paso de tiempo
• Una regla de transición, una función que toma como entrada una asignación de estados para las celdas de un único mosaico y produce como salida otra asignación de estados para las mismas celdas.

En cada paso de tiempo, la regla de transición se aplica de manera simultánea y sincrónica a todos los mosaicos de la partición. Luego, la partición se desplaza y la misma operación se repite en el siguiente paso de tiempo, y así sucesivamente. De esta manera, como sucede con cualquier autómata celular, el patrón de estados de las células cambia con el tiempo para realizar algún cálculo o simulación no trivial.

El esquema de partición más simple es probablemente el vecindario de Margolus , llamado así por Norman Margolus , quien estudió por primera vez los autómatas celulares de bloques utilizando esta estructura de vecindario. En el vecindario de Margolus, la red se divide en bloques de 2 celdas (o cuadrados de 2 × 2 en dos dimensiones, o cubos de 2 × 2 × 2 en tres dimensiones, etc.) que se desplazan una celda (a lo largo de cada dimensión) en pasos de tiempo alternos. ^{[1] [2] [3]}

Una técnica estrechamente relacionada debida a K. Morita y M. Harao ^[4] consiste en dividir cada célula en un número finito de partes, cada parte siendo dedicada a algún vecino. La evolución procede intercambiando las partes correspondientes entre vecinos y luego aplicando en cada célula una transformación puramente local que depende sólo del estado de la célula (y no de los estados de sus vecinos). Con tal esquema de construcción, se garantiza que el autómata celular sea reversible si la transformación local es en sí misma una biyección . Esta técnica puede verse como un autómata celular en bloque en una red más fina de células, formada por las partes de cada célula más grande; los bloques de esta red más fina alternan entre los conjuntos de partes dentro de una sola célula grande y los conjuntos de partes en células vecinas que comparten partes entre sí. ${\estilo de visualización F}$${\estilo de visualización F}$

Mientras la regla para la evolución de cada bloque sea reversible , el autómata entero también lo será. Más fuertemente, en este caso, el comportamiento invertido en el tiempo del autómata también puede describirse como un autómata celular de bloques, con la misma estructura de bloques y con una regla de transición que invierte la regla del autómata original dentro de cada bloque. Lo inverso también es cierto: si los bloques no son reversibles individualmente, la evolución global no puede ser reversible: si dos configuraciones diferentes x e y de un bloque conducen al mismo estado de resultado z , entonces una configuración global con x en un bloque sería indistinguible después de un paso de la configuración en la que x es reemplazada por y . Es decir, un autómata celular es reversible globalmente si y solo si es reversible a nivel de bloque. ^[5]

La facilidad de diseñar autómatas celulares de bloques reversibles y de probar la reversibilidad de los autómatas celulares de bloques contrasta fuertemente con los autómatas celulares con otras estructuras de vecindad que no sean de bloques, para las cuales es indecidible si el autómata es reversible y para las cuales la dinámica inversa puede requerir vecindades mucho más grandes que la dinámica directa. ^[6] Cualquier autómata celular reversible puede ser simulado por un autómata celular de bloques reversible con un mayor número de estados; sin embargo, debido a la indecidibilidad de la reversibilidad para los autómatas celulares que no sean de bloques, no hay un límite computable en el radio de las regiones en el autómata que no sea de bloques que corresponden a los bloques en la simulación, y la traducción de una regla que no sea de bloques a una regla de bloques tampoco es computable. ^[7]

Los autómatas celulares en bloque también son un formalismo conveniente para diseñar reglas que, además de la reversibilidad, implementen leyes de conservación como la conservación del número de partículas, la conservación del momento, etc. Por ejemplo, si la regla dentro de cada bloque preserva el número de células vivas en el bloque, entonces la evolución global del autómata también preservará el mismo número. Esta propiedad es útil en las aplicaciones de los autómatas celulares a la simulación física. ^[8]

Como escriben Toffoli y Margolus, ^[2] el modelo de autómata celular de bloque no introduce ninguna potencia adicional en comparación con un autómata celular convencional que utiliza la misma estructura de vecindad en cada paso de tiempo: cualquier autómata celular de bloque puede simularse en un autómata celular convencional utilizando más estados y una vecindad más grande. Específicamente, dejemos que los dos autómatas utilicen la misma red de celdas, pero dejemos que cada estado del autómata convencional especifique el estado del autómata de bloque, la fase de su patrón de desplazamiento de partición y la posición de la celda dentro de su bloque. Por ejemplo, con la vecindad de Margolus, esto aumentaría el número de estados en un factor de ocho: hay cuatro posiciones posibles que una celda puede tomar en su bloque 2 × 2 , y dos fases para la partición. Además, dejemos que la vecindad del autómata convencional sea la unión de los bloques que contienen la celda dada en el autómata celular de bloque. Luego, con esta estructura de vecindad y estado, cada actualización del autómata de bloque puede ser simulada por una única actualización del autómata celular convencional.

Los autómatas celulares de bloque se utilizan comúnmente para implementar gases reticulares y otras simulaciones cuasifísicas, debido a la facilidad de simular restricciones físicas como las leyes de conservación en estos sistemas. ^{[1] [8]} Por ejemplo, el modelo de Margolus puede utilizarse para simular el modelo de gas reticular HPP, en el que las partículas se mueven en dos direcciones perpendiculares y se dispersan en ángulos rectos cuando chocan entre sí. En la simulación celular de bloque de este modelo, la regla de actualización mueve cada celda a la celda diagonalmente opuesta en su bloque, excepto en el caso de que una celda contenga dos partículas diagonalmente opuestas, en cuyo caso se reemplazan por el par complementario de partículas diagonalmente opuestas. De esta manera, las partículas se mueven diagonalmente y se dispersan de acuerdo con el modelo HPP. ^{[2] [9]} Una regla alternativa que simula el modelo de gas reticular HPP con movimiento horizontal y vertical de partículas, en lugar de con movimiento diagonal, implica rotar el contenido de cada bloque en sentido horario o antihorario en fases alternas, excepto nuevamente en el caso de que una celda contenga dos partículas diagonalmente opuestas, en cuyo caso permanece inalterado. ^[2] En cualquiera de estos modelos, el momento (la suma de los vectores de velocidad de las partículas en movimiento) se conserva, así como su número, una propiedad esencial para simular gases físicos. Sin embargo, los modelos HPP son poco realistas como modelo de dinámica de gases, porque tienen reglas de conservación no físicas adicionales: el momento total dentro de cada línea de movimiento, así como el momento total del sistema general, se conserva. Los modelos más complejos basados ​​en la cuadrícula hexagonal evitan este problema. ^[9]

Estos autómatas también pueden utilizarse para modelar el movimiento de los granos de arena en montones de arena y relojes de arena . En esta aplicación, se puede utilizar un vecindario de Margolus con una regla de actualización que preserva el número de granos dentro de cada bloque de 2 × 2 pero que mueve cada grano lo más abajo posible dentro de su bloque. Si un bloque incluye dos granos que están apilados verticalmente uno sobre el otro, la función de transición del autómata lo reemplaza por un bloque en el que los granos están uno al lado del otro, lo que en efecto permite que los montones de arena altos se caigan y se extiendan. Este modelo no es reversible, pero aún obedece a una ley de conservación sobre el número de partículas. ^[10] Una regla modificada, que utiliza el mismo vecindario pero mueve las partículas lateralmente en la medida de lo posible, así como hacia abajo, permite que los montones de arena simulados se extiendan incluso cuando no son muy empinados. ^[11] También son posibles modelos de montones de arena de autómatas celulares más sofisticados, que incorporan fenómenos como el transporte por viento y la fricción. ^[10]

La aplicación original de Margolus para el modelo de autómata celular de bloques fue simular el modelo de bola de billar de computación reversible, en el que las señales lógicas booleanas se simulan mediante partículas en movimiento y las puertas lógicas se simulan mediante colisiones elásticas de esas partículas. Es posible, por ejemplo, realizar cálculos de bolas de billar en el modelo bidimensional de Margolus, con dos estados por celda y con el número de celdas vivas conservado por la evolución del modelo. En la regla "BBM" que simula el modelo de bola de billar de esta manera, las señales consisten en celdas vivas individuales, que se mueven en diagonal. Para lograr este movimiento, la función de transición de bloques reemplaza un bloque que contiene una sola celda viva por otro bloque en el que la celda se ha movido a la esquina opuesta del bloque. De manera similar, las colisiones elásticas pueden realizarse mediante una función de transición de bloques que reemplaza dos celdas vivas diagonalmente opuestas por las otras dos celdas del bloque. En todas las demás configuraciones de un bloque, la función de transición de bloques no realiza ningún cambio en su estado. En este modelo, rectángulos de 2 × 4 de células vivas (cuidadosamente alineados con respecto a la partición) permanecen estables y pueden usarse como espejos para guiar las trayectorias de las partículas en movimiento. Por ejemplo, la ilustración del vecindario de Margolus muestra cuatro partículas y un espejo; si el siguiente paso utiliza la partición azul, entonces dos partículas se están moviendo hacia el espejo mientras que las otras dos están a punto de colisionar, mientras que si el siguiente paso utiliza la partición roja, entonces dos partículas se están alejando del espejo y las otras dos acaban de colisionar y se alejarán una de la otra. ^{[3] [5] [12]}

Toffoli y Margolus ^[2] sugieren dos reglas más reversibles para el vecindario de Margolus con celdas de dos estados que, si bien no están motivadas por consideraciones físicas, conducen a dinámicas interesantes.

En la regla de los "Critters", la función de transición invierte el estado de cada célula de un bloque, excepto en el caso de un bloque con exactamente dos células vivas, que permanece inalterado. Además, los bloques con tres células vivas experimentan una rotación de 180 grados, así como la inversión de estado. ^[2] Esta es una regla reversible y obedece a las leyes de conservación del número de partículas (contando una partícula como una célula viva en fases pares y como una célula muerta en fases impares) y a la paridad del número de partículas a lo largo de líneas diagonales. ^[12] Debido a que es reversible, los estados iniciales en los que todas las células adoptan estados elegidos aleatoriamente permanecen sin estructurar a lo largo de su evolución. Sin embargo, cuando se comienza con un campo más pequeño de células aleatorias centradas dentro de una región más grande de células muertas, esta regla conduce a dinámicas complejas similares a las del Juego de la vida de Conway, en el que muchos patrones pequeños similares al planeador de la vida escapan del área aleatoria central e interactúan entre sí. ^{[2] [12]} A diferencia de los planeadores de Life, la reversibilidad y la conservación de partículas juntas implican que cuando los planeadores chocan entre sí en Critters, al menos uno debe escapar, y a menudo estos choques permiten que ambos planeadores entrantes se reconstituyan en diferentes trayectorias de salida. Por medio de tales colisiones, esta regla también puede simular el modelo de bola de billar de la computación, aunque de una manera más compleja que la regla BBM. ^{[12] La regla Critters también puede admitir} naves espaciales más complejas de velocidades variables, así como osciladores con infinitos períodos diferentes. ^[13]

En la regla de "Tron", la función de transición deja cada bloque sin cambios excepto cuando las cuatro celdas tienen el mismo estado, en cuyo caso sus estados se invierten. Ejecutar esta regla desde condiciones iniciales en forma de un rectángulo de celdas vivas, o desde formas simples similares con bordes rectos, conduce a patrones rectilíneos complejos. Toffoli y Margolus también sugieren que esta regla se puede utilizar para implementar una regla de sincronización local que permite simular cualquier autómata celular de bloque vecino de Margolus utilizando un autómata celular asincrónico . En esta simulación, cada celda de un autómata asincrónico almacena tanto un estado para el autómata simulado como un segundo bit que representa la paridad de una marca de tiempo para esa celda; por lo tanto, el autómata asincrónico resultante tiene el doble de estados que el autómata que simula. Las marcas de tiempo están restringidas a diferir en como máximo uno entre celdas adyacentes, y cualquier bloque de cuatro celdas cuyas marcas de tiempo tengan todas la paridad correcta se puede actualizar de acuerdo con la regla de bloque que se está simulando. Cuando se realiza una actualización de este tipo, las paridades de las marcas de tiempo también deben actualizarse según la regla de Tron, que necesariamente preserva la restricción de las marcas de tiempo adyacentes. Al realizar actualizaciones locales de esta manera, la evolución de cada celda en el autómata asincrónico es idéntica a su evolución en el autómata de bloque sincrónico que se está simulando. ^{[2] [14]}

• Secuencia del palillo de dientes , un patrón fractal que puede ser emulado por autómatas celulares con el vecindario de Margolus

• Simulación de criaturas, Seth Koehler, Universidad de Florida