Autómatas celulares

Autómata celular
Autómata celular

El comportamiento de la hormiga de Langton, a la que dedicamos el artículo anterior, en una cuadrícula con todas las casillas en blanco como situación de partida, es muy peculiar. Al principio forma patrones sencillos, pero tras unos cientos de movimientos aparece una gran estructura compacta y de aspecto desordenado, como se puede ver en la ilustración de la semana pasada. Y lo más sorprendente es que luego, a partir de los diez mil movimientos, aparece una “avenida” en alguna de las direcciones diagonales (NE, NO, SE o SO), generada por una secuencia de 104 pasos que se repite indefinidamente.

Al parecer, y aunque aún no se ha podido demostrar de forma concluyente, sea cual fuere la configuración de partida la hormiga acaba generando una de estas avenidas infinitas (conjetura de Cohen-Kong). Lo que sí se ha demostrado, contestando a una de las preguntas de la semana pasada, es que el “hormiguero” generado por la hormiga siempre crece indefinidamente, sea cual fuere la configuración de partida (la demostración, dada por el teorema de Bunimovitch-Troubetzkoy, es sencilla pero farragosa, y se encuentra fácilmente en la red).

La hormiga confinada y la hormiga 3D

¿Y si la hormiga de Langton se moviera en una cuadrícula finita?

Imaginemos una hormiga en una de las casillas centrales de un tablero de ajedrez como posición de partida. Cuando topa con un borde, la hormiga “rebota” y queda en la misma casilla, pero con la flecha apuntando en dirección contraria; ¿qué configuración obtendríamos después de n movimientos? Y si en vez de “rebotar la hormiga sale por el otro lado, es decir, pasa al otro extremo de la misma fila o columna, como si saliera del borde opuesto, ¿qué pasaría en este caso?

También podemos sustituir la cuadrícula por una “cubícula”, una red tridimensional de celdillas cúbicas; pero para que la hormiga pueda desplazarse también en vertical, tenemos que modificar las reglas. ¿De qué manera podemos hacerlo?

Otros autómatas

La hormiga de Langton y sus variantes, así como los distintos patrones del juego de la vida (osciladores, vidas estáticas, naves espaciales, etc.) y el juego en sí mismo son “autómatas celulares”, objetos matemáticos y computacionales que no es fácil definir en pocas palabras, aunque sí visualizarlos. En general, el autómata celular tiene como base una cuadrícula (aunque también puede ser una rejilla hexagonal, triangular, etc.) cuyas celdillas -las “células”- pueden hallarse en distintos estados (generalmente dos), que varían de acuerdo con unas reglas sencillas.

Por ejemplo, en el caso del juego de la vida, como vimos, cada célula puede hallarse en dos estados, “viva” o “muerta”, y ese estado depende de las células vecinas, que pueden mantenerla viva, resucitarla o matarla, ya sea por soledad o por superpoblación.

Invito a mis sagaces lectores a inventar sus propios autómatas celulares, o a introducir alguna variante en los ya existentes. Solo hace falta una hoja de papel cuadriculado y un poco de imaginación (aunque un buen programa informático puede ser de gran ayuda).

Carlo Frabetti es escritor y matemático, miembro de la Academia de Ciencias de Nueva York. Ha publicado más de 50 obras de divulgación científica para adultos, niños y jóvenes, entre ellos ‘Maldita física’, ‘Malditas matemáticas’ o ‘El gran juego’. Fue guionista de ‘La bola de cristal’.

Puedes seguir a Materia en Facebook, Twitter, Instagram o suscribirte aquí a nuestra newsletter