Rastrillo (autómata celular)

Un rastrillo , en el léxico de los autómatas celulares , es un tipo de tren de sopladores , que es un autómata que deja tras de sí un rastro de escombros. Sin embargo, en el caso de un rastrillo, los escombros que quedan son una corriente de naves espaciales , ^{[ 1 ]} que son autómatas que "viajan" recorriendo una serie corta de iteraciones y terminan en una nueva ubicación después de que cada ciclo regresa a la configuración original.

Una selección de rastrillos en El juego de la vida de Conway

En el Juego de la Vida de Conway , el descubrimiento de los rastrillos fue uno de los componentes clave necesarios para formar el reproductor , el primer patrón conocido en la Vida en el que el número de células vivas exhibe un crecimiento cuadrático . Un reproductor se forma al disponer varios rastrillos de manera que los planeadores —las naves espaciales más pequeñas posibles— que generan interactúen para formar una secuencia de cañones de planeadores , patrones que emiten planeadores. Los planeadores emitidos llenan un triángulo creciente del plano del juego. ^{[ 2 ]} De manera más general, cuando existe un rastrillo para una regla de autómata celular (una función matemática que define la siguiente iteración que se derivará de una configuración particular de células vivas y muertas), a menudo se pueden construir sopladores que dejan rastros de muchos otros tipos de objetos, al colisionar las corrientes de naves espaciales emitidas por múltiples rastrillos que se mueven en paralelo. ^{[ 3 ]} Como escribe David Bell:

Son extremadamente importantes en la vida porque su salida se puede usar para construir otros objetos y transmitir señales para realizar operaciones lógicas. Siempre que se encuentra un nuevo motor de combustión interna, un objetivo importante es "domesticarlo" para que su escape "sucio" e inútil se convierta en un escape "limpio", especialmente en el caso de los planeadores. ^{[ 4 ]}

El primer rastrillo descubierto a principios de la década de 1970 fue el "rastrillo espacial", que se mueve con una velocidad de c /2 (o una unidad cada dos pasos), emitiendo un planeador cada veinte pasos. ^{[ 5 ]} Para Life, ahora se conocen rastrillos que se mueven ortogonalmente con velocidades de c /2, c /3, c /4, c /5, 2c / 5, 2c / 7, c /10 ^{[ 6 ]} y 17c /45, y diagonalmente con velocidades de c / 4 y c /12, con muchos períodos diferentes. ^{[ 7 ]} También se conocen rastrillos para otros autómatas celulares similares a la vida , incluidos Highlife , ^{[ 8 ]} Day & Night , ^{[ 9 ]} y Seeds . ^{[ 10 ]}

Gotts (1980) demuestra que el rastrillo espacial en Life puede formarse mediante una "secuencia de colisión estándar" en la que un único planeador interactúa con un conjunto ampliamente separado de semillas iniciales de 3 células ( parpadeos y bloques ). Como consecuencia, halla límites inferiores para la probabilidad de que estos patrones se formen en cualquier condición inicial aleatoria suficientemente dispersa y suficientemente grande para Life. Este resultado conduce a secuencias de colisión estándar para muchos otros patrones, como los reproductores. ^{[ 11 ]}