La m¨¢quina de Turing

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?

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?

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