La Asociación de Maquinaria de Computación (ACM) el miércoles anunció que ha otorgado la AM de este año premio turinga menudo denominado Premio Nobel de Computación, al científico informático y matemático Avi Wigderson del Instituto de Estudios Avanzados de Princeton.
Wigderson fue reconocido por sus contribuciones fundamentales que impulsaron lo que se conoce como la Teoría de la Computación, con especial distinción en «remodelar nuestra comprensión del papel de la aleatoriedad en la computación» y «décadas de liderazgo intelectual en la informática teórica», dijo la ACM.
También: Los algoritmos pronto controlarán tu vida y la arruinarán si se entrenan incorrectamente
El premio, que lleva el nombre del matemático e informático británico Alan M. Turing, cuenta con un premio de 1 millón de dólares y cuenta con el apoyo financiero de Google.
Wigderson, profesor Herbert H. Maass en Princeton, ha demostrado durante décadas una profunda comprensión de la computación como algo más que simples máquinas. La computación es un fenómeno que se encuentra en todo el universo.
«La computación es una noción realmente fundamental», dijo Wigderson en una entrevista con ZDNET. «No se trata sólo de algoritmos en las computadoras: todo calcula.»
«Cuando ves una concha en la playa, con algún patrón notable, que fue calculado mediante pasos extremadamente simples: creció a partir de un grano y, localmente, estos granos calcularon los granos vecinos y se conectaron; este proceso realmente simple, Si lo evolucionas, obtendrás algunos patrones sorprendentes».
Estas reglas simples de cambio local e incremental – «que conocemos muy bien», dijo Wigderson – «pueden crear fenómenos muy complejos». Abundan los ejemplos computacionales. La computación es cómo el óvulo fertilizado llega a ser un ser humano, o cómo las células humanas se dividen a lo largo de la vida. «Además, chismes», añadió Wigderson. «Cuando cuentas algo que te dijeron a ti o en Facebook, la forma en que evoluciona la información, son preguntas computacionales que pueden enmarcarse en modelos computacionales completos».
Otorgar el premio Turing a Wigderson es especialmente apropiado porque su campo, la Teoría de la Computación, fue iniciado por Turing en 1936 con su papel emblemático«Sobre números computables, con una aplicación al Entscheidungsproblem».
Turing sentó las bases para la definición extremadamente amplia de computación como una evolución de un entorno a través de cambios incrementales locales, donde el «entorno» puede ser seres humanos, galaxias, conchas en la playa, información o cualquier número de fenómenos.
También: Jack Dongarra, que hizo utilizables las supercomputadoras, recibe el premio ACM Turing 2021
Visto a través de la lente de Turing, tal como lo plantearon Wigderson y sus colegas durante décadas, todo fenómeno natural es computación. «La forma en que las termitas construyen estos castillos, o las abejas, que de alguna manera saben dónde ir a buscar miel, en realidad evolucionan para crear, a pesar de que tienen células cerebrales muy pequeñas», explicó Wigderson.
El premio reconoce a Wigderson específicamente por su contribución a la comprensión del papel que juega la aleatoriedad en la computación. Las computadoras convencionales, desde las mainframes hasta los iPhones, son «deterministas»; es decir, siguen un patrón predecible de pasos. Pero muchos de los ejemplos más intrigantes de computación en la naturaleza involucran elementos de aleatoriedad, desde la concha marina hasta la bandada de estorninos conocida como murmuración.
Wigderson y sus colaboradores utilizaron la exploración de la aleatoriedad para avanzar en la comprensión de qué problemas pueden y no pueden calcularse «eficientemente». Hay numerosos problemas en el mundo (en ciencia, matemáticas e ingeniería) para los cuales no se conocen algoritmos eficientes, es decir, un algoritmo que pueda operar en «tiempo polinómico», en lugar de tiempo exponencial.
También: El legado perdurable de Alan Turing: 10 ideas más allá de Enigma
Por ejemplo, la factorización de números enteros grandes en sus factores primos no tiene un algoritmo conocido que pueda ejecutarse en un tiempo inferior al exponencial. Pero no basta con encontrar dicho algoritmo; Los informáticos y matemáticos quieren probarpara saber con certeza, de una forma u otra, si existe podría existe una solución para problemas tan «difíciles».
Los tres artículos principales citados por la ACM forman una secuencia, una progresión, dijo Wigderson a ZDNET.
«La pregunta era cuán poderosa es la aleatoriedad en los algoritmos», dijo Wigderson. A partir de los años ochenta, los científicos informáticos habían encontrado muchas formas de utilizar la aleatoriedad como ruta hacia algoritmos eficientes, «Y entonces, parecía que la aleatoriedad es muy poderosa».
«Estos trabajos pretendían demostrar que la aleatoriedad no es tan poderosa», afirmó. En cambio, Wigderson y sus colegas desarrollaron generadores de números pseudoaleatorios que podrían resolver algunos problemas difíciles de una manera eficiente y determinista.
«En todos estos artículos, se toma un problema difícil y se crea un generador pseudoaleatorio que puede generar de manera determinista bits que parecen aleatorios, y se pueden reemplazar entradas aleatorias en un algoritmo probabilístico. [and fashion] uno determinista.»
También: Científicos informáticos famosos
La eliminación de la aleatoriedad, sustituyéndola por un enfoque determinista, culminó en el artículo final con el generador pseudoaleatorio más sofisticado. La lección, señaló Wigderson: «Podríamos concluir que cualquier algoritmo probabilístico de tiempo polinomial puede convertirse en uno determinista de tiempo polinomial».
Un efecto secundario sorprendente de esos descubrimientos es que si se puede eliminar la aleatoriedad de un algoritmo, se puede demostrar la dureza del problema, una manera sorprendente de resolver la cuestión de si un problema es o no difícil. .
«De alguna manera, estos dos conceptos [randomness and hardness], que son muy diferentes, están íntimamente conectados», dijo Wigderson. «Son casi lo mismo. Eliminar la aleatoriedad de los algoritmos probabilísticos y demostrar la dureza de los problemas computacionales son, en cierto modo, problemas duales».
Para aquellos que deseen profundizar más en el trabajo sobre la aleatoriedad, los artículos se enumeran a continuación. Sin embargo, puede leer el capítulo sobre aleatoriedad en el gran volumen de Wigderson, «Math and Computation». que está disponible como descarga gratuita. Si hojeas ese libro, estarás muy por encima de la mayoría de las personas en tu próximo cóctel.
- «Dureza versus aleatoriedad» (En coautoría con Noam Nisan)
Entre otros hallazgos, este artículo introdujo un nuevo tipo de generador pseudoaleatorio y demostró que la simulación determinista eficiente de algoritmos aleatorios es posible bajo supuestos mucho más débiles de lo que se conocía anteriormente.
Para Wigderson, de 67 años, el placer de descubrir conexiones sorprendentes fue un impulso impulsor desde una edad temprana.
También: IA en sesenta segundos
«Siempre me encantaron las matemáticas desde la primera infancia», dijo Wigderson. «Mi papá me interesaba por los rompecabezas y esas cosas».
Wigderson se graduó en el Technion (Instituto de Tecnología) de Israel y obtuvo una maestría y un doctorado en informática de la Universidad de Princeton. Una conmovedora charla sobre sus experiencias se ofrece en el libro de Wigderson. discurso de aceptación el año pasado cuando recibió un doctorado honorario del Technion.
«Realmente me importa formalizar los modelos computacionales», dijo Wigderson sobre lo que atrae su interés, «por ejemplo, si algún protocolo criptográfico es seguro o el tiempo de ejecución de algún algoritmo es tal o cual.
«El hecho de que trate esta noción fundamental, pero en realidad sea un campo matemático, es para mí muy valioso».
Entre los logros de los que está más orgulloso, dijo Wigderson, está su trabajo para promover lo que se llama «pruebas de conocimiento cero», donde la información puede mantenerse en secreto pero dos contrapartes pueden llegar a un acuerdo. «Digamos que sé algo, sé quién ganará las elecciones, y ustedes no me creen y estoy tratando de convencerlos. [that I really do]. Hay una manera de convencerte sin decirte nada que no sepas».
De hecho, tal situación es la raíz de la criptografía de clave pública, donde cada parte mantiene oculta su clave privada pero es capaz de convencer a la otra de que ha firmado con autoridad un contrato electrónico, por ejemplo. «Es una noción totalmente paradójica», dijo Wigderson sobre estas pruebas de conocimiento cero. «Este es el tipo de cosas que te deja boquiabierto al pensar que algo así podría existir».
Los equilibrios intelectuales de Wigderson deleitan con un agudo sentido del significado subyacente. La cuestión de qué problemas son demostrablemente difíciles, por ejemplo, tiene mucho en juego para la sociedad.
Tal como se formuló en la década de 1970, la frase «¿P = NP?» pregunta si un problema cuya solución puede verificarse también podría, en última instancia, resolverse mediante una ecuación de tiempo polinomial: resolverse de manera eficiente. Si es así, entonces probablemente se podría construir una computadora para resolver algunos de los problemas aparentemente intratables del mundo en períodos de tiempo prácticos.
«Es una de las preguntas intelectuales más fundamentales jamás formuladas», dijo Wigderson de P = NP. Su conjetura personal, que es consensuada en su campo, es que P no es NP igual, es decir, algunos problemas no se pueden resolver de manera eficiente.
«Si todo el mundo está equivocado y P es igual a NP, las consecuencias son sorprendentes», afirmó Wigderson. «Prácticamente cualquier problema que quieras resolver, puedes resolverlo de manera eficiente; cualquier cosa; puedes curar el cáncer».
Sin embargo, «si P no es igual a NP, las implicaciones para cosas que están fuera de nuestro alcance son bastante significativas», dijo Wigderson. Por un lado, significaría que algunos elementos del pensamiento humano, como la creatividad, bien podrían estar fuera del alcance de las computadoras porque no hay manera de simular eficientemente la heurística, el sentido humano de las cosas que intervienen, por ejemplo, en la creación artística. .
Pero el vaso está medio lleno, en otro sentido: si los problemas de NP no pueden resolverse eficientemente, significa que la criptografía (la base entera de la economía moderna) está a salvo de ser descifrada, señaló Wigderson.
También: El nuevo test de Turing: ¿eres humano?
Si P es igual o no a NP es una cuestión abierta. «Esperaba ver a alguien demostrarlo en mi vida, pero ahora lo dudo», dijo Wigderson.
La computadora cuántica tampoco es la respuesta fácil a ese punto muerto. «Piense en una computadora cuántica: esto no existe», dijo Wigderson. «No sabemos si alguna vez existirá», a pesar de que IBM, Google y otros lo teorizan intensamente.
Si P = NP es un problema abierto, también lo es la pregunta del momento: ¿Qué puede hacer o no hacer la IA (incluidas las máquinas de «inteligencia artificial general») para igualar el pensamiento humano? Ciertamente, la noción de que todo en el universo se computa implica que la IA debería ser capaz de alcanzar cierta medida de la capacidad humana.
También: El verdadero objetivo de la IA puede que ya no sea la inteligencia
«Nosotros somos carbono y ellos silicio, por lo que el material es diferente, pero las dificultades están en el nivel psicológico, no en el operativo», opina Wigderson. La IA ya ha demostrado que «puede resolver muchos problemas que antes no sabíamos cómo resolver», dijo Wigderson. Conoce a «algunos matemáticos destacados que están empezando a utilizar estos dispositivos como colaboradores» en la demostración de teoremas y cosas similares.
«Lo que es más interesante para mí es lo que no pueden hacer», afirmó. «¿Cuáles son los límites de este tipo de ordenador?» Uno de esos límites es la relativa escasez de datos necesarios para entrenar modelos de IA para algunos problemas.
También: ¿Puede la IA generativa resolver el mayor problema sin resolver de la informática?
«Por ejemplo, diseñar una nueva teoría matemática como la relatividad o Maxwell [Maxwell’s Equations] — para estos, hay muchos menos ejemplos, ¿verdad? Así que creo que este tipo de avance teórico será más difícil para estas máquinas porque no hay muchos datos».
Para las muchas implicaciones de que P sea igual o no igual a NP, Wigderson se contenta con dejar que una nueva generación lidere el camino.
«Me estoy divirtiendo con los postdoctorados del instituto, todos son brillantes, estoy colaborando con algunos de ellos y aprendiendo de los más jóvenes», dijo. «Es muy agradable estar en esta situación rodeado de gente joven que te mantiene aprendiendo».