Gusanos de Paterson

Los gusanos de Paterson son una  familia de autómatas celulares tipo tyurmita inventados en 1971 por el científico británico Mike Paterson para simular el comportamiento y la alimentación de algunos gusanos prehistóricos . A pesar de un conjunto simple de reglas, el comportamiento de los autómatas puede ser muy complejo, y para uno de los conjuntos de reglas se desconoce su destino.  

Antecedentes

Los gusanos prehistóricos se alimentaban de sedimentos en el fondo de los estanques y evitaban repetir sus caminos porque había poca comida. Sin embargo, la comida se encontró en montones, por lo que tendían a permanecer cerca de los caminos que ya habían recorrido. Al mismo tiempo, diferentes tipos de gusanos tenían diferentes reglas que determinaban qué tan cerca de los caminos pasados ​​permanecer, cuándo y cómo girar bruscamente [1] .

En 1969, David Raup y Adolf Zeilacher crearon  una simulación por computadora de huellas de gusanos fósiles, lo que inspiró a Paterson y John Conway a buscar modelos de autómatas celulares simples para estudiar gusanos idealizados en una red [2] . Conway propuso estudiar gusanos en una cuadrícula , pero solo había tres tipos de gusanos con un comportamiento bastante aburrido, y Paterson sugirió usar una cuadrícula triangular.

Descripción

En este modelo, el gusano se arrastra a lo largo de un enrejado triangular , cuyos bordes representan comida, y cuando pasa el borde, se pinta ("come") [3] . En cada vértice, el gusano elige qué cara se moverá en función de cuál de las seis caras adyacentes al vértice esté llena. Las direcciones se cuentan desde el punto de vista del gusano [1] . El gusano muere si el vértice no tiene caras sin rellenar ("sin comer"), lo que, sin embargo, solo es posible en el estado inicial debido a consideraciones de paridad [4] .

Las reglas están predeterminadas y definen un autómata celular específico en la familia (el " tipo de gusano"), sin embargo, a menudo se asume que el gusano toma una decisión en cada paso, pero si ya se ha encontrado con una situación similar, debe hacerlo. tomar la misma decisión.

Numeración de reglas

Las reglas se pueden clasificar especificando las direcciones que toma el gusano cuando "encuentra" por primera vez una situación desconocida, en el orden en que ocurren estas situaciones. Las direcciones generalmente se numeran en el sentido de las agujas del reloj, comenzando desde 0, la dirección hacia adelante, vea la imagen a la izquierda [5] . En este caso, el gusano no puede elegir la dirección 3: dar la vuelta. Además, normalmente no hay elecciones que el gusano no tenga que hacer, ya que muere antes, y se considera que el gusano hace el primer giro a la derecha, ya que el caso de un giro a la izquierda es simétrico [1] .

Por ejemplo, la regla {2, 2, 0}, que especifica el gusano que se muestra a la derecha, dice que en las dos primeras opciones (las 5 direcciones no están sombreadas) el gusano gira hacia la derecha y en la tercera (la derecha) -la dirección hacia atrás está sombreada y las direcciones hacia la izquierda están sombreadas) adelante, izquierda-atrás y derecha-atrás, respectivamente) selecciona el movimiento hacia adelante. No se indican más opciones, ya que el gusano vuelve al principio por tercera vez y muere. Si nos limitamos a los casos en los que el gusano hace el primer giro a la derecha, entonces hay potencialmente 1296 reglas posibles [6] . Sin embargo, teniendo en cuenta el hecho de que el gusano a menudo muere antes de que tenga tiempo de hacer todas las elecciones posibles y, por lo tanto, no tiene sentido distinguir estas reglas, solo hay 412 de ellas [4] . Entre ellos, 336 son finitos, 73 son infinitos y se repiten cíclicamente con un desplazamiento, para dos, el infinito no se ha probado, pero se supone (estas son las reglas {1,0,4,2,0,2,0} y {1,0,4,2,0 ,1,5}), y se desconoce el comportamiento de otro (regla {1,0,4,2,0,1,5}) [4] .

Notas

1. ↑ 1 2 3 Beeler, Gusano de Michael Paterson . Instituto de Tecnología de Massachusetts (junio de 1973). Consultado el 15 de agosto de 2008. (indefinido)
2. ↑ Los gusanos de Paterson . mundo wolframmath. Consultado el 15 de agosto de 2008. (indefinido)
3. ↑ Hayes, Brian. En busca del alimentador de fondo escoria óptimo  // Científico  estadounidense  :revista. — Sigma Xi, la Sociedad de Investigación Científica. — vol. 95 , núm. 5 . - Pág. 392-396 . -doi : 10.1511 / 2003.5.392 .
4. ↑ 1 2 3 Chaffin, Gusanos de Benjamin Paterson . Archivado desde el original el 7 de junio de 2011. (indefinido)
5. ↑ Pegg Jr., Ed Math Games: Paterson's Worms Revisited . MAA en línea (27 de octubre de 2003). Consultado el 15 de agosto de 2008. Archivado desde el original el 23 de marzo de 2004. (indefinido)
6. ↑ Gardner, Martin (1986), Rosquillas anudadas y otros entretenimientos matemáticos , W. H. Freeman, ISBN 978-0-7167-1799-7