Los gusanos de Paterson son una familia de autómatas celulares ideados en 1971 por Mike Paterson y John Horton Conway para modelar el comportamiento y los patrones de alimentación de ciertos gusanos prehistóricos. En el modelo, un gusano se mueve entre puntos de una cuadrícula triangular a lo largo de segmentos de línea que representan la comida. Sus giros están determinados por la configuración de segmentos de línea comidos y no comidos adyacentes al punto en el que se encuentra el gusano en ese momento. A pesar de estar regido por reglas simples, el comportamiento de los gusanos puede ser extremadamente complejo, y el destino final de una variante aún se desconoce.
Los gusanos fueron estudiados a principios de la década de 1970 por Paterson, Conway y Michael Beeler, descritos por Beeler en junio de 1973, [1] y presentados en noviembre de 1973 en la columna "Juegos matemáticos" de Martin Gardner en Scientific American . [2]
El juego Worms? de Electronic Arts de 1983 es una implementación interactiva de los gusanos de Paterson, donde cada vez que un gusano tiene que girar en una dirección para la cual no existe una regla, se detiene y permite al usuario elegir una dirección, que establece esa regla para ese gusano.
Los gusanos de Paterson son un intento de simular el comportamiento de los gusanos prehistóricos. Estas criaturas se alimentaban de sedimentos en el fondo de los estanques y evitaban volver a recorrer los caminos que ya habían recorrido porque allí el alimento escaseaba, pero, como el alimento se encontraba en parches, a los gusanos les convenía permanecer cerca de los senderos que habían recorrido anteriormente. Las distintas especies de gusanos tenían distintas reglas innatas respecto de cuán cerca de los senderos recorridos debían permanecer, cuándo girar y cuán brusco debía ser el giro. [1] En 1969, Raup y Seilacher crearon simulaciones por ordenador de los senderos fosilizados de los gusanos, y estas simulaciones inspiraron a Paterson y Conway a desarrollar un conjunto simple de reglas para estudiar gusanos idealizados en cuadrículas regulares. [3]
El modelo original de Conway era un gusano en una cuadrícula ortogonal, pero esto produjo solo tres especies diferentes de gusanos, todos con un comportamiento bastante poco interesante. Paterson consideró gusanos en una cuadrícula triangular. [1] Los gusanos de Paterson fueron descritos por Beeler en un memorando de IA del Instituto Tecnológico de Massachusetts (#[1]) y fueron presentados en noviembre de 1973 en la columna " Juegos matemáticos " de Martin Gardner en Scientific American , [2] y luego reimpresos en Gardner 1986. [4] Estas simulaciones diferían en el enfoque de otros autómatas celulares desarrollados en la misma época, que se centraban en las células y las relaciones entre ellas. [5] Los modelos informáticos simples como estos son demasiado abstractos para describir con precisión el comportamiento de las criaturas reales, pero sí demuestran que incluso reglas muy simples pueden dar lugar a patrones que se asemejan a sus huellas. [6]
El gusano comienza en algún punto de una cuadrícula triangular infinita. Empieza a moverse a lo largo de una de las seis líneas de cuadrícula que se encuentran en cada punto [6] y, una vez que ha recorrido una unidad de distancia, llega a un nuevo punto. El gusano decide entonces, basándose en la distribución de líneas de cuadrícula atravesadas y no atravesadas, qué dirección tomará. Las direcciones son relativas al punto de vista del gusano. Si el gusano no se ha encontrado con esta distribución exacta antes, puede partir por cualquier línea de cuadrícula no atravesada. A partir de ese momento, si se encuentra con esa distribución nuevamente, debe moverse de la misma manera. Si no hay líneas de cuadrícula no atravesadas disponibles, el gusano muere y la simulación termina. [1]
Existen muchos tipos diferentes de gusanos, según la dirección en la que giran cuando se encuentran con un nuevo tipo de intersección. Las diferentes variedades de gusanos se pueden clasificar sistemáticamente asignando un número a cada dirección y enumerando la elección realizada cada vez que se encuentra con un nuevo tipo de intersección. [7]
Las seis direcciones están numeradas de la siguiente manera:
Por lo tanto, la dirección 0 indica que el gusano continúa viajando en línea recta, la dirección 1 indica que el gusano hará un giro de 60° a la derecha y lo mismo ocurre con las otras direcciones. El gusano no puede viajar en la dirección 3 porque esa es la línea de cuadrícula que acaba de atravesar. Por lo tanto, un gusano con la regla {1,0,5,1} decide viajar en la dirección 1 la primera vez que tiene que hacer una elección, en la dirección 0 la próxima vez que tiene que hacer una elección y así sucesivamente. Si solo hay una línea de cuadrícula disponible, el gusano no tiene más opción que tomarla y esto generalmente no se indica explícitamente.
Un gusano cuyo conjunto de reglas comienza con 0 continúa en línea recta para siempre. Este es un caso trivial, por lo que generalmente se estipula que el gusano debe girar cuando encuentra un punto con solo líneas de cuadrícula sin recorrer. Además, para evitar duplicados simétricos en forma de imagen especular, el primer giro del gusano debe ser hacia la derecha. [1] Un gusano muere si regresa a su origen una tercera vez, porque entonces no hay bordes sin recorrer disponibles. Solo el origen puede ser letal para el gusano. [8]
Hay 1.296 combinaciones posibles de reglas de gusano. [4] Esto se puede ver mediante el siguiente argumento:
Por lo tanto, hay 2 × 4 × 81 × 2 × 1 = 1296 combinaciones diferentes de reglas. Muchas de ellas son duplicados en espejo de otras, y otras mueren antes de tener que hacer todas las elecciones en su conjunto de reglas, dejando 411 especies distintas (412 si se incluye el gusano de línea recta infinita). [8] 336 de estas especies finalmente mueren. 73 patrones muestran un comportamiento infinito, es decir, se establecen en un patrón repetitivo que no regresa al origen. Se cree firmemente que otros dos son infinitos y uno permanece sin resolver. Once de las reglas muestran un comportamiento complicado. No mueren ni siquiera después de muchos miles de millones de iteraciones, ni adoptan un patrón obviamente infinito. Su destino final fue desconocido hasta 2003, cuando Benjamin Chaffin desarrolló nuevos métodos para resolverlas. Después de muchas horas de tiempo de computadora, nueve de las once reglas se resolvieron, dejando a los gusanos con las reglas {1,0,4,2,0,2,0} y {1,0,4,2,0,1,5}. [7] El primero de ellos fue resuelto por Tomas Rokicki, quien determinó que se detiene después de 57 billones (5,7×10 13 ) de pasos de tiempo, dejando solo {1,0,4,2,0,1,5} sin resolver. Según Rokicki, el gusano sigue activo después de 5,2×10 19 pasos de tiempo. Utilizó un algoritmo basado en Hashlife de Bill Gosper para simular los gusanos a velocidades extraordinarias. [8] Este comportamiento es considerablemente más complejo que el del gusano de cuadrícula rectangular relacionado, que tiene un camino más largo de solo 16 segmentos. [6]
Es posible que dos especies diferentes de gusanos produzcan el mismo camino, aunque no necesariamente lo recorran en el mismo orden. [1] El camino más común es también el más corto: el símbolo de siete puntos de la prueba MOT / refugio antiatómico . [4] Un ejemplo de este camino se muestra en la figura animada anterior. En total, hay 299 caminos diferentes y 209 de ellos son producidos por una sola especie. [1]
