La hormiga de Langton, de la que nos hemos ocupado en semanas anteriores, es también una máquina de Turing
Por: CARLO FRABETTI
Foto: Alan Turing, de joven.
Nos preguntábamos la semana pasada de qué forma habría que modificar las reglas de la hormiga de Langton para que se desplazara por una rejilla tridimensional. La solución es sencilla, pero el resultado muy complejo: basta con introducir dos nuevos colores. En la rejilla bidimensional, hay celdillas de dos colores -blancas y negras- y cada color indica un sentido de giro. Si colocamos la hormiga en una rejilla cúbica con celdillas de cuatro colores, por ejemplo, blancas, negras, azules y rojas, y a cada color le corresponde una dirección de giro -derecha, izquierda, arriba y abajo- la hormiga se moverá en 3D. También hay que ajustar, obviamente, los cambios de color de las casillas al visitarlas la hormiga.
El estudio de las evoluciones de la hormiga 3D requiere mucho más tiempo y potencia de cómputo que en el caso de su prima bidimensional, y no hay al respecto (que yo sepa) teoremas o conjeturas sólidas, aunque parece ser que también tiende a generar “avenidas” infinitas.
En los comentarios 9 y 69-75 de la semana pasada, Carlos Maeso y Luca Tanganelli ofrecen interesantes aportaciones informáticas al juego de la vida y la hormiga de Langton respectivamente.
La hormiga de Turing
No podemos despedirnos de la hormiga de Langton sin mencionar que es también -o ante todo- una máquina de Turing.
La máquina de Turing (una de las más interesantes definiciones -o formalizaciones- del concepto de algoritmo, dicho sea de paso) es un aparato mental ideado por Alan Turing en los años treinta del pasado siglo para dar respuesta a una de las grandes preguntas planteadas por el matemático David Hilbert en 1900.
En el Congreso Internacional de Matemáticas celebrado en París en 1900. Hilbert presentó una lista de 23 grandes problemas no resueltos (algunos de los cuales siguen sin resolver 120 años después), de algunos de los cuales se desprende la pregunta a la que Turing se propuso dar respuesta: ¿Son «decidibles» las matemáticas? Es decir, ¿existe algún método definido -un algoritmo- que, dada una sentencia matemática cualquiera, nos permita decidir si es verdadera o falsa?
Maqueta en el museo Bletchley Park de la máquina ideada por Alan Turing para descifrar Enigma.
La máquina de Turing es sumamente sencilla, y se puede visualizar de la siguiente manera: una cinta de papel tan larga como se desee puede correr en ambas direcciones bajo un cabezal de lectura/escritura que, en cada paso, lee el signo (un 0 o un 1 en la versión más simple) que hay en ese lugar de la cinta y, según el «estado» de la máquina en ese momento, lo cambia por otro signo o no. Con su sencillo dispositivo mental, Turing demostró -en sintonía con Gödel- que las matemáticas son indecidibles, a la vez abrió un apasionante debate, que aún persiste, sobre la inteligencia artificial.
¿Por qué podemos afirmar que la hormiga de Langton es una máquina de Turing? ¿De qué manera afecta al concepto de máquina de Turing el hecho de que la hormiga no se mueva sobre una cinta sino sobre una cuadrícula bidimensional? O, viceversa, ¿cómo sería la versión unidimensional de la hormiga de Langton?
Autor: 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’.