El programa de Hilbert

Es f¨¢cil ver que la hormiga de Langton es una m¨¢quina de Turing, tal como se coment¨® la semana pasada, si pensamos que la propia hormiga es la cabeza de lectura/escritura de la m¨¢quina, que ¡°lee¡± el color de la celdilla que visita y lo modifica, e incluso podemos visualizar las sucesivas celdillas visitadas formando una cinta continua, ya que la hormiga siempre pasa de una celdilla a una contigua, y la hormiga movi¨¦ndose sobre un conjunto de celdillas adyacentes es equivalente a una sucesi¨®n de celdilla...

Es f¨¢cil ver que la hormiga de Langton es una m¨¢quina de Turing, tal como se coment¨® la semana pasada, si pensamos que la propia hormiga es la cabeza de lectura/escritura de la m¨¢quina, que ¡°lee¡± el color de la celdilla que visita y lo modifica, e incluso podemos visualizar las sucesivas celdillas visitadas formando una cinta continua, ya que la hormiga siempre pasa de una celdilla a una contigua, y la hormiga movi¨¦ndose sobre un conjunto de celdillas adyacentes es equivalente a una sucesi¨®n de celdillas pasando bajo la misma.

No tan evidente es que la hormiga de Langton sea una m¨¢quina universal de Turing, es decir, que todo lo computable algor¨ªtmicamente se pueda computar en la hormiga de Langton. De hecho, esto no se demostr¨® hasta el a?o 2000, catorce a?os despu¨¦s de la creaci¨®n de la hormiga (quienes deseen profundizar en el tema pueden consultar, por ejemplo, el art¨ªculo Complexity of Langton¡¯s ante, Gajardo, Moreira y Goles, 2002).

Un programa ambicioso

En la lista de 23 problemas que David Hilbert present¨® en el Congreso Internacional de Matem¨¢ticas de Par¨ªs, en 1900, ya est¨¢ presente su preocupaci¨®n por la formalizaci¨®n rigurosa de las matem¨¢ticas, como vimos al hablar de la m¨¢quina de Turing; pero esta preocupaci¨®n tom¨® forma definitiva m¨¢s tarde, en lo que se ha llamado el ¡°programa de Hilbert¡±.

En los a?os veinte del pasado siglo, Hilbert se propuso establecer un conjunto de axiomas completo y coherente, libre de paradojas y ambig¨¹edades, sobre el que fundamentar toda la matem¨¢tica, de modo que, dada cualquier proposici¨®n, pudiera demostrarse su veracidad o falsedad en funci¨®n de esos axiomas. Pero el teorema de incompletitud de G?del dio al traste con este ambicioso proyecto, al demostrar que en un sistema l¨®gico de cierta complejidad, como las matem¨¢ticas, siempre habr¨¢ proposiciones indecidibles dentro del propio sistema.

El conjunto de todos los conjuntos normales, ?es normal o anormal?

Una manera menos t¨¦cnica de mostrar la dificultad de una formalizaci¨®n exenta de ambig¨¹edades la encontramos en la paradoja de Russell sobre la teor¨ªa de conjuntos. Llamemos conjuntos ¡°normales¡± a los que no se contienen a s¨ª mismos, y ¡°anormales¡± a los que se contienen a s¨ª mismos. Por ejemplo, un conjunto de l¨¢pices no es un l¨¢piz, luego es normal, y un conjunto de redes -como internet, la red de redes- puede ser a su vez una red, es decir, un conjunto anormal. La pregunta es: el conjunto de todos los conjuntos normales, ?es normal o anormal? Si es normal, hay que incluirlo en el conjunto de los conjuntos normales, luego se contiene a s¨ª mismo, luego es anormal, y si es anormal, no est¨¢ incluido en el conjunto de los conjuntos normales, luego no se incluye a s¨ª mismo, luego es normal¡­

Una versi¨®n popular de esta paradoja es la famosa paradoja del barbero, difundida por el propio Russell:

En un pueblo hay un barbero que afeita a todos los que no se afeitan a s¨ª mismos y solo a ellos. ?Se afeita a s¨ª mismo el barbero? Si lo hace, afeita a alguien que se afeita a s¨ª mismo, y si no lo hace, deja de afeitar a alguien que no se afeita a s¨ª mismo¡­

Invito a mis sagaces lectoras/es a explicar la paradoja del barbero, y a buscar otros conjuntos anormales y otras formulaciones de la paradoja de Russell. Que, por cierto, es una variante de la paradoja de Cantor sobre el conjunto de todos los conjuntos. Pero ese es otro art¨ªculo.

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