¿Están las computadoras listas para resolver este problema matemático notoriamente difícil de manejar?

Sra. Tecnología | SuperRembo a través de codificación de tren

La científica informática Marijn Heule siempre está al acecho de un buen desafío matemático. Profesor asociado en la Universidad Carnegie Mellon, Heule tiene una reputación impresionante en la resolución de problemas matemáticos intratables con herramientas computacionales. Su resultado de 2016 con el problema de los triples pitagóricos booleanos fue una enorme prueba que acaparó los titulares: La prueba matemática de doscientos terabytes es la más grande jamás vista . Ahora está implementando un enfoque automatizado para atacar la seductora y simple conjetura de Collatz.

Propuesto por primera vez (según algunos relatos) en la década de 1930 por el matemático alemán Lothar Collatz, este problema de teoría de números proporciona una receta, o algoritmo, para generar un número secuencia : Comience con cualquier número entero positivo. Si el número es par, se divide por dos. Si el número es impar, multiplica por tres y suma uno. Y luego haz lo mismo, una y otra vez. La conjetura afirma que la secuencia siempre terminará en 1 (y luego continuará cíclicamente a través de 4, 2, 1).

El número 5, por ejemplo, genera solo seis términos:

5, 16, 8, 4, 2, 1

El número 27 recorre 111 términos, oscilando hacia arriba y hacia abajo (en su altura alcanza los 9232) antes de aterrizar finalmente en el 1.

El número 40 genera otra breve secuencia:

40, 20, 10, 5, 16, 8, 4, 2, 1

Hasta la fecha, la conjetura ha sido verificada por computadora para todos los valores iniciales hasta casi 300 billones de billones y cada número finalmente llega a 1.

La mayoría de los investigadores creen que la conjetura es cierta. Ha atraído a multitudes de matemáticos y no matemáticos por igual, pero nadie ha producido una demostración. A principios de la década de 1980, el matemático húngaro Paul Erdős declaró: Las matemáticas aún no están preparadas para tales problemas.

Lo que queremos saber es si los humanos o las computadoras son mejores para resolver tales problemas.

Marijn Heule

Y probablemente tenga razón, dice Heule. Para Heule, el atractivo de Collatz no es tanto la perspectiva de un gran avance como el avance de las técnicas de razonamiento automatizado. Después de jugar con él durante cinco años, Heule y sus colaboradores, Scott Aaronson y Emre Yolcu, publicaron recientemente un papel en el servidor de preimpresión arXiv. Aunque no logramos probar la conjetura de Collatz, escriben, creemos que las ideas aquí representan un nuevo enfoque interesante.

Es un fracaso noble, dice Aaronson, científico informático de la Universidad de Texas en Austin. Un fracaso porque no probaron la conjetura. Noble porque hicieron progresos en otro sentido: Heule lo ve como un punto de partida para determinar si los humanos o las computadoras son mejores para probar tales problemas.

Traducir las matemáticas a la computación

Para muchos problemas matemáticos, las computadoras son inútiles, ya que no tienen acceso a la vasta obra matemática acumulada a lo largo de la historia. Pero a veces las computadoras sobresalen donde los humanos no tienen remedio. Dígale a una computadora cómo se ve una solución, asígnele un objetivo y un espacio de búsqueda bien definido, y luego, con fuerza bruta, la computadora podría encontrarla. Aunque es cuestión de debate si los resultados computacionales equivalen a adiciones significativas al canon matemático. La visión tradicional es que solo la creatividad y la intuición humanas, a través de conceptos e ideas, amplían el alcance de las matemáticas, mientras que los avances a través de la informática a menudo se descartan como ingeniería.

Historia relacionada

Este algoritmo puede decir qué secuencias numéricas le resultarán interesantes a un humano El resultado sugiere que algún día las máquinas podrían ser entrenadas para detectar la elegancia y la belleza matemática.

En cierto sentido, la computadora y la conjetura de Collatz son una combinación perfecta. Por un lado, como señala Jeremy Avigad, lógico y profesor de filosofía en Carnegie Mellon, la noción de un algoritmo iterativo está en la base de la informática, y las secuencias de Collatz son un ejemplo de un algoritmo iterativo, procediendo paso a paso de acuerdo con a una regla determinista. De manera similar, mostrar que un proceso termina es un problema común en informática. Los informáticos generalmente quieren saber que sus algoritmos terminan, es decir, que siempre devuelven una respuesta, dice Avigad. Heule y sus colaboradores están aprovechando esa tecnología para abordar la conjetura de Collatz, que en realidad es solo un problema de terminación.

La belleza de este método automatizado es que puede encender la computadora y esperar.

jeffrey lagarias

La experiencia de Heule es con una herramienta computacional llamada solucionador SAT, o solucionador de satisfacibilidad, un programa de computadora que determina si existe una solución para una fórmula o problema dado un conjunto de restricciones. Aunque de manera crucial, en el caso de un desafío matemático, un solucionador de SAT primero necesita traducir o representar el problema en términos que la computadora entienda. Y como dice Yolcu, estudiante de doctorado de Heule: La representación importa mucho.

Un tiro largo, pero vale la pena intentarlo

Cuando Heule mencionó por primera vez cómo abordar a Collatz con un solucionador de SAT, Aaronson pensó: De ninguna manera esto va a funcionar. Pero se convenció fácilmente de que valía la pena intentarlo, ya que Heule vio formas sutiles de transformar este viejo problema que podría hacerlo maleable. Se dio cuenta de que una comunidad de científicos informáticos estaba usando solucionadores SAT para encontrar con éxito pruebas de terminación para una representación abstracta de computación llamada sistema de reescritura. Era una posibilidad remota, pero le sugirió a Aaronson que transformar la conjetura de Collatz en un sistema de reescritura podría hacer posible obtener una prueba de terminación para Collatz (Aaronson había ayudado previamente a transformar la hipótesis de Riemann en un sistema computacional, codificándolo en un pequeño Turing máquina). Esa noche, Aaronson diseñó el sistema. Era como una tarea, un ejercicio divertido, dice.

'En un sentido muy literal, estaba luchando contra un Terminator, al menos un probador del teorema de terminación'.

scott aaronson

El sistema de Aaronson capturó el problema de Collatz con 11 reglas. Si los investigadores pudieran obtener una prueba de terminación para este sistema análogo, aplicando esas 11 reglas en cualquier orden, eso probaría que la conjetura de Collatz es cierta.

Heule probó con herramientas de última generación para probar la terminación de los sistemas de reescritura, lo que no funcionó; fue decepcionante, si no tan sorprendente. Estas herramientas están optimizadas para problemas que se pueden resolver en un minuto, mientras que cualquier enfoque para resolver Collatz probablemente requiera días, si no años, de computación, dice Heule. Esto proporcionó motivación para perfeccionar su enfoque e implementar sus propias herramientas para transformar el problema de reescritura en un problema SAT.

Una representación del sistema de reescritura de 11 reglas para la conjetura de Collatz.

HUELLA MARINA

Aaronson pensó que sería mucho más fácil resolver el sistema sin una de las 11 reglas, dejando un sistema similar al de Collatz, una prueba de fuego para el objetivo más grande. Lanzó un desafío humano contra computadora: el primero en resolver todos los subsistemas con 10 reglas gana. Aaronson lo intentó a mano. Heule lo intentó con el solucionador SAT: codificó el sistema como un problema de satisfacibilidad, con otra capa inteligente de representación, traduciendo el sistema a la jerga de la computadora de variables que pueden ser 0 y 1, y luego dejó que su solucionador SAT se ejecutara en los núcleos. , en busca de evidencia de terminación.

El sistema aquí sigue la secuencia de Collatz para el valor inicial 27—27 está en la parte superior izquierda de la cascada diagonal, 1 está en la parte inferior derecha. Hay 71 pasos, en lugar de 111, ya que los investigadores usaron una versión diferente pero equivalente del algoritmo de Collatz: si el número es par, se divide por 2; de lo contrario, multiplique por 3, agregue 1 y luego divida el resultado por 2.

HUELLA MARINA

Ambos lograron probar que el sistema termina con varios conjuntos de 10 reglas. A veces era una empresa trivial, tanto para el ser humano como para el programa. El enfoque automatizado de Heule tomó como máximo 24 horas. El enfoque de Aaronson requirió un esfuerzo intelectual significativo, tomó algunas horas o incluso un día: un conjunto de 10 reglas que nunca logró probar, aunque cree firmemente que podría haberlo hecho, con más esfuerzo. En un sentido muy literal, estaba luchando contra un Terminator, dice Aaronson, al menos un probador del teorema de terminación.

Desde entonces, Yolcu ha perfeccionado el solucionador SAT, calibrando la herramienta para que se ajuste mejor a la naturaleza del problema de Collatz. Estos trucos marcaron la diferencia: aceleraron las pruebas de terminación para los subsistemas de 10 reglas y redujeron los tiempos de ejecución a meros segundos.

La pregunta principal que queda, dice Aaronson, es: ¿Qué pasa con el conjunto completo de 11? Intenta ejecutar el sistema en el conjunto completo y simplemente funciona para siempre, lo que tal vez no debería sorprendernos, porque ese es el problema de Collatz.

Tal como lo ve Heule, la mayor parte de la investigación en razonamiento automatizado hace la vista gorda ante problemas que requieren muchos cálculos. Pero en base a sus avances anteriores, cree que estos problemas pueden resolverse. otros tienen Collatz transformado tener tiene sistema de reescritura , pero es la estrategia de manejar un solucionador de SAT afinado a escala con una potencia de cómputo formidable lo que podría ganar tracción hacia una prueba.

Hasta ahora, Heule ha llevado a cabo la investigación de Collatz utilizando alrededor de 5000 núcleos (las unidades de procesamiento que alimentan las computadoras; las computadoras de consumo tienen cuatro u ocho núcleos). Como becario de Amazon, tiene una invitación abierta de Amazon Web Services para acceder a recursos prácticamente ilimitados, hasta un millón de núcleos. Pero es reacio a usar mucho más.

Quiero alguna indicación de que este es un intento realista, dice. De lo contrario, Heule siente que estaría desperdiciando recursos y confianza. No necesito un 100% de confianza, pero realmente me gustaría tener alguna evidencia de que hay una posibilidad razonable de que tenga éxito.

Supercargando una transformación

La belleza de este método automatizado es que puedes encender la computadora y esperar, dice el matemático Jeffrey Lagarias, de la Universidad de Michigan. Ha jugado con Collatz durante unos cincuenta años y se ha convertido en guardián del conocimiento, compilando bibliografías comentadas y editando un libro sobre el tema. El último desafío. Para Lagarias, el enfoque automatizado le trajo a la mente una papel de 2013 por el matemático de Princeton John Horton Conway, quien reflexionó que el problema de Collatz podría estar entre una clase esquiva de problemas que son verdaderos e indecidibles, pero a la vez no demostrablemente indecidibles. Como señaló Conway: ... incluso podría ser que la afirmación de que no son demostrables no sea demostrable en sí misma, y ​​así sucesivamente.

Si Conway tiene razón, dice Lagarias, no habrá pruebas, automatizadas o no, y nunca sabremos la respuesta.

Podría decirse que el humano que más se ha acercado es el matemático Terence Tao, de la Universidad de California, Los Ángeles. En 2019, Tao demostró que la conjetura de Collatz es casi cierto para casi todos los números (casi se basa en dos definiciones técnicas diferentes, sin embargo, de acuerdo con el significado en inglés simple).

Tao cree que una prueba humana de la conjetura tendría más significado matemático: llegar al por qué de ella— que una prueba de computadora. Pero que un problema importante sin resolver recaiga en un probador automatizado podría potenciar una transformación revolucionaria en la forma en que los matemáticos utilizan la asistencia informática en su trabajo, dice. Con un problema tan intratable como este, tomaremos cualquier información que podamos obtener.

Sin embargo, lo que Heule y sus colaboradores realmente buscan es un escenario en el que, utilizando este enfoque, con este problema, la computadora tenga éxito donde falla el ser humano, o viceversa. En este punto, no sabemos si estas técnicas son mucho más fuertes que lo que los humanos pueden hacer a mano o no, o si los humanos pueden hacer cosas que la computadora no puede hacer, dice Heule. Lo que queremos saber es si los humanos o las computadoras son mejores para resolver tales problemas.

Con ese fin, veamos quién resuelve primero la conjetura de Collatz.

esconder