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 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