Critters

Critters es un autómata celular de bloques reversible con dinámicas similares al Juego de la Vida de Conway, descrito por primera vez por Tommaso Toffoli y Norman Margolus en 1987. Definición Critters se define en una cuadrícula infinita bidimensional de celdas, que puede identificarse con la red de enteros. Como en el Juego de la Vida de Conway, en cualquier momento cada celda puede estar en uno de dos estados: viva o muerta. La regla de Critters es un autómata celular de bloques que utiliza el vecindario de Margolus. Esto significa que, en cada paso, las celdas del autómata se dividen en bloques de 2 × 2 y cada bloque se actualiza independientemente de los demás bloques. El centro de un bloque en un paso de tiempo se convierte en la esquina de cuatro bloques en el siguiente paso de tiempo, y viceversa; de esta manera, las cuatro celdas en cada bloque pertenecen a cuatro bloques de 2 × 2 diferentes de la partición anterior. La función de transición para Critters cuenta el número de celdas vivas en un bloque, y si este número es exactamente dos deja el bloque sin cambios. Si el número de celdas vivas es cero, uno o cuatro, la función de transición invierte el estado de cada celda en el bloque. Y finalmente, si el número de celdas vivas es exactamente tres, la transición invierte cada estado y luego rota todo el bloque 180°. Como la función que combina estas operaciones es invertible, el autómata definido por estas reglas es un autómata celular reversible. Como las celdas en bloques alejados de los bloques activos oscilarán entre vivas y muertas en generaciones sucesivas, todo el campo parecerá "parpadear". En algunas implementaciones de Critters, este parpadeo se elimina invirtiendo la imagen (pero no los estados de las celdas) en generaciones numeradas impares. Una versión alternativa de la función de transición invierte los estados solo en bloques con exactamente dos celdas vivas, y en pasos de tiempo alternos rota los bloques con tres celdas vivas o los bloques con una celda viva. A diferencia de la función de transición original, esta preserva el número de celdas vivas en cada paso, pero lleva a un comportamiento dinámico equivalente a la versión original de la función, sin necesidad del paso de inversión de imagen. (Es decir, las dos versiones son iguales, hasta invertir todos los estados cada otra generación.)