NINGÚN ALGORITMO PUEDE RECONOCER ALGUNAS FORMAS DE CUATRO DIMENSIONES
Algunas preguntas no tienen receta. No porque nadie la haya encontrado todavía, sino porque está demostrado que ningún algoritmo —ningún procedimiento paso a paso, por largo que sea, ejecutado en cualquier ordenador— puede responderlas correctamente siempre. Cameron McA. Gordon, de la Universidad de Texas en Austin, añade dos preguntas de este tipo sobre formas de cuatro dimensiones.
¿Es la misma forma?
Los matemáticos llaman a estas formas 4-variedades: espacios que, vistos de cerca, se parecen en todas partes al espacio ordinario de cuatro dimensiones. Para entregárselas a un ordenador, el artículo supone que están construidas a partir de piezas planas pegadas entre sí («lineales a trozos», o PL), de modo que cada una puede describirse mediante una lista finita de datos. La pregunta básica es entonces: dadas dos de estas formas, ¿son iguales, salvo deformación continua?
En 1958, A. A. Markov demostró que esta pregunta no tiene algoritmo. La demostración de Markov convierte el problema de las formas en un problema sobre grupos: existen grupos, definidos por un número finito de reglas, para los que ningún algoritmo puede decidir si una combinación dada de sus elementos es igual a la identidad: el «problema de la palabra». A partir de un grupo así, se pueden construir formas que un algoritmo solo podría distinguir resolviendo ese problema imposible.
Cuenta atrás hasta siete
El argumento de Markov llega incluso a concentrar la dificultad en formas concretas. Toma S², la superficie de una bola corriente, y forma el producto S² × S², una forma de cuatro dimensiones. Pega k copias de ella (una «suma conexa», que se escribe #k). Para algún k, ningún algoritmo puede decidir si una forma dada es #k(S² × S²). ¿Qué k?
El artículo repasa la cuenta atrás. Un grupo con un problema de la palabra irresoluble y 12 reglas, encontrado por Borisov en 1969, dio 14 copias. Gordon lo bajó a 12 en 2022. M. Tancer encontró una nueva vía, a través de la clasificación de Freedman de las formas de cuatro dimensiones, y llegó a 9 en la versión «topológica», en la que las formas no tienen por qué estar construidas a partir de piezas planas. Una versión anterior de este trabajo llegó a 8. Después, Kegel, Li y Ren construyeron un grupo irresoluble mucho más pequeño —3 generadores y 9 reglas—, que llegó a 7 en la versión topológica y a 9 en la de piezas planas.
Gordon hace que la vía de Tancer funcione también para las formas construidas a partir de piezas planas, y demuestra:
No existe ningún algoritmo para decidir si una 4-variedad dada es la misma, pieza a pieza, que la suma conexa de 7 copias de S² × S².
El núcleo de la demostración es un diccionario. Para cada palabra w del grupo de Kegel, Li y Ren, Gordon construye una forma de cuatro dimensiones. Si w es igual a la identidad, una sucesión de movimientos permitidos sobre las reglas —los movimientos de Andrews-Curtis, que reescriben la descripción sin cambiar la forma— demuestra que la forma es exactamente siete copias de S² × S². Si no lo es, la forma contiene lazos que no pueden contraerse hasta un punto —algo que nunca ocurre en siete copias de S² × S²—, así que no puede ser esas siete copias. Un algoritmo que reconociera #7(S² × S²) resolvería, por tanto, el problema de la palabra, lo cual es imposible.
Esferas anudadas
La segunda pregunta trata de nudos. Un nudo ordinario es una circunferencia enredada en el espacio de tres dimensiones, y decidir si un nudo puede deshacerse es posible: existe un algoritmo, debido a Haken. Una dimensión más arriba, una esfera de dos dimensiones puede anudarse dentro del espacio de cuatro dimensiones. En dimensiones superiores, se sabe que el problema correspondiente no tiene algoritmo. Para las esferas de dos dimensiones en la esfera de cuatro dimensiones S⁴, nadie lo sabe.
Gordon demuestra que, dentro de #7(S² × S²), no existe ningún algoritmo para decidir si una esfera de dos dimensiones —o cualquier superficie, orientable o no— está desanudada. Por el camino, el artículo construye en esa forma una esfera cuyo espacio circundante tiene un grupo con un problema de la palabra irresoluble y, en 12 copias de S² × S², una esfera cuyo grupo contiene una copia de todo grupo que pueda describir un ordenador.
El premio: cero copias
El artículo enuncia el objetivo sin rodeos: reducir el número de copias a cero. Cero copias significa la propia esfera de cuatro dimensiones, S⁴. En cinco dimensiones o más, ningún algoritmo puede reconocer la esfera; en dos y tres dimensiones, uno sí puede. Las cuatro dimensiones siguen siendo una cuestión abierta, igual que la de si las esferas anudadas en S⁴ pueden detectarse. Cada copia eliminada acerca ambas preguntas.