La vida como lógico | Noticias

Martin Davis, nacido en 1928, ha sido testigo del desarrollo de la informática desde su nacimiento. No mucho después de obtener su doctorado. en matemáticas de la Universidad de Princeton en 1950, donde su asesor era el matemático y lógico Alonzo Church, Davis se encontró programando la Computadora Automática Variable Discreta Ordnance (ORDVAC) en la Universidad de Illinois. Pasó la mayor parte de su carrera en la Universidad de Nueva York (NYU), donde fue uno de los miembros fundadores del departamento de informática.

Hoy, aunque vive en Berkeley, CA, Davis es profesor emérito en el Departamento de Ciencias de la Computación y el Instituto Courant de Ciencias Matemáticas, en NYU.

Lo más cercano al corazón de Davis es la lógica matemática, que proporciona la base teórica para todo lo computacional. Ha tenido una obsesión de toda la vida con el Décimo Problema de Hilbert (H10), que solicita un algoritmo que pueda decidir si cualquier ecuación diofántica tiene una solución en los números enteros (una ecuación diofántica es una ecuación polinómica con coeficientes enteros).

En su tesis doctoral, Davis formuló lo que más tarde se denominó «la atrevida hipótesis de Davis», que forjó un vínculo entre la lógica y la teoría de números. Hizo la hipótesis de que los conjuntos recursivamente enumerables (aquellos cuyos miembros pueden enumerarse mediante un algoritmo) y los conjuntos diofantinos (aquellos que son el rango de una función diofántica) son los mismos. Si lo fueran, se deduciría inmediatamente que el H10 no tiene solución.

En su trabajo con las matemáticas Hilary Putnam y Julia Robinson, Davis hizo avances significativos para confirmar la atrevida hipótesis. Ese trabajo permitió al matemático y científico informático ruso Yuri Matiyasevich agregar la pieza final al rompecabezas en 1970 y demostrar que el H10 no tiene solución.

MCCA habló con Davis en el verano de 2021, unos meses después de su 93 cumpleaños. Lo que sigue es una versión editada de la conversación.

Eres escéptico de la conjetura de que P es diferente de NP. ¿Puedes contarme sobre eso?

La gente piensa en la clase NP como una especie de análogo a los conjuntos recursivamente enumerables. La analogía se basa en suponer que la computabilidad en tiempo polinomial es un análogo de la computabilidad, que la computabilidad en tiempo polinomial es factible computabilidad. ¿Por qué crees eso? Ciertamente no es cierto en ningún sentido razonable. Si tiene un límite de polinomio de alto grado con un coeficiente numérico grande, no es particularmente factible computacionalmente en absoluto. La clase tiene buenas propiedades matemáticas de cierre. Ciertamente es una clase interesante, pero ¿por qué identificarla con la viabilidad?

Hay algoritmos de tiempo exponencial que, en el ámbito en el que se emplean, son bastante útiles y funcionan bien. Cuando doy charlas sobre esto, cito los resultados de Margaret Wright. Al principio se pensó que la programación lineal no era de tiempo polinómico. Se consideró un gran avance cuando se encontró un algoritmo de tiempo polinomial para la programación lineal, ¡pero ese algoritmo no funcionó muy bien! Como mostró Margaret Wright, el método simplex, que es exponencial en los peores casos, es mejor y más rápido en muchos casos.

Parte de mi escepticismo también se relaciona con mi experiencia con el Décimo Problema de Hilbert, donde estaba muy claro que la gente no tiene ninguna intuición sobre los polinomios de alto grado.

Por cierto, no sé cuál es su razonamiento, pero Donald Knuth está de acuerdo conmigo en que de ninguna manera es un caso abierto y cerrado que P y NP sean diferentes. Yo digo que apostaría 50-50.

¿Qué pasa con los problemas NP-completos?

Creo que los problemas NP-completos son problemas difíciles, sin duda alguna. No creo que nadie vaya a encontrar un algoritmo agradable, lindo y rápido para ningún problema de NP-completo. Eso no significa que no puedan encontrar un algoritmo de tiempo polinomial, tal vez simplemente no uno muy factible. Siempre al acecho detrás de estos argumentos heurísticos está la idea de que «tiempo polinomial» y «factible» son la misma cosa.

¿Cuál sería una mejor forma de definir la viabilidad?

Supongo que si tuvieras uno, tu‘Estaría escribiendo un papel sobre él.

Derecha. No está claro que exista una noción muy precisa sobre la que puedas poner los dedos. Puede ser que algunos algoritmos sean más difíciles que otros, y solo haya un rango.

Además, lo que es factible depende en parte de las instalaciones informáticas que tenga disponibles. Para mi libro La computadora universal¹, Quería ilustrar la idea de convergencia con el número π. Entonces escribí un programa que usaba la serie de Leibniz π / 4 = 1 – 1/3 + 1/5 – 1/7 … y lo calculé tal vez a 20,000 términos. No hace mucho tiempo, la idea de calcular π sumando 20.000 términos en la serie de Leibniz habría parecido completamente tonta. Y, sin embargo, era algo que un aficionado, como yo lo soy en lo que respecta al cálculo numérico, podría hacer fácilmente con una herramienta que tenía en casa y un poco de conocimiento sobre cómo escribir un programa de computadora.

Mencionaste tu libro La computadora universal. En la edición de 2018, agregó material nuevo sobre aprendizaje automático e inteligencia artificial. ¿Qué es lo que más te ha sorprendido del aprendizaje automático?

Que estos modelos de redes neuronales eran tan útiles y que podían funcionar tan bien. Había sido un escéptico de las redes neuronales durante muchos años. La idea original era que estamos imitando cerebros. Y pensé: ‘Es solo otro modelo, no tiene ninguna virtud especial’. Pero, de hecho, para algunos problemas, como ganar en el juego Go, funciona asombrosamente bien. Allí, mi intuición estaba totalmente equivocada.

No existe una teoría de por qué el aprendizaje automático funciona tan bien. ¿Crees que alguna vez existirá tal teoría?

No creo que sea tan misterioso. Es un proceso de convergencia, una aproximación sucesiva, el tipo de cosas que se han utilizado durante años en el análisis. Converge rápidamente si elige la función correcta en la construcción de la red neuronal multinivel, por lo que no creo que haya una teoría profunda especial involucrada. Sospecho que realmente estamos imitando a la naturaleza.

Para convertirte en un pianista virtuoso, practicas siete horas al día. ¿Por qué no puedes simplemente leer un manual que te dice, «para ser un pianista virtuoso, esto es lo que tienes que hacer»? Eso no funciona. Te sientas al piano, acudes a un maestro, incluso si eres un profesional, que observa lo que haces y te dice: «No, tu meñique se desvaneció un poco». Es un proceso de convergencia.

En este momento, la inteligencia artificial está explotando en términos de producción de investigación y sus usos en la sociedad. ¿Es esto algo positivo o algo que hay que temer?

Me acerco a la pregunta de esta manera: ¿Podemos hacer un autómata que pueda hacer todas las cosas que hacemos y quizás hacerlas mejor? Con juegos difíciles como el Go y el ajedrez, sí, podemos. Ya no puedes vencer a las máquinas.

Esto se relaciona con la cuestión de cómo hacemos estas cosas nosotros mismos, y realmente no lo sabemos. ¿Realmente el cerebro lleva a cabo algoritmos? Ciertamente hace cosas que, cuando hacemos que un autómata las haga, usamos algoritmos. Nuestro cerebro obviamente realiza búsquedas. Intentamos recordar un dato y no aparece de inmediato, pero esperamos un rato y de repente aparece. Y ciertamente, sabemos que la computación universal no necesita mucho. Stephen Wolfram ha convertido casi en una religión de culto el hecho de que la computación universal está disponible en entidades muy pequeñas. Si, de hecho, el cerebro hace todas estas cosas maravillosas mediante la ejecución de algoritmos, entonces, por supuesto, podremos fabricar computadoras que hagan lo mismo.

Hay un tipo en la Universidad Rice que ha hablado de esto. Cual es su nombre…?

Moshe Vardi?

Si. ¡Mira, acabas de hacer una búsqueda! Dice que no hay duda de que en una generación tendremos máquinas que pueden hacer todo lo que la gente puede hacer. Eso puede ser un poco demasiado optimista.

Si observa los asombrosos logros de estas redes neuronales, lo único que no hacen es proponer nuevas ideas. La pregunta es hasta qué punto está sucediendo algo de nivel superior en nuestro cerebro que es, por así decirlo, una tecnología completamente diferente. No lo creo. Sospecho que es más de lo mismo, en otro nivel. Después de todo, llegamos a ser buenos matemáticos haciendo muchas matemáticas.

Entonces, ¿cómo explica las intuiciones o los saltos de imaginación que hacen los grandes matemáticos cuando perciben una nueva estructura o conectan dos cosas que parecían muy diferentes? Hiciste eso con Hilbert‘s Décimo problema, cuando pensaba que los conjuntos enumerables recursivamente y los conjuntos diofantinos podrían ser lo mismo.

Bueno, después de todo, uno era un subconjunto del otro, por lo que no era como conectar dos cosas completamente diferentes. Era más como extender el alcance de algo que parecía muy limitado. ¡Era el entusiasmo de un niño tanto como cualquier otra cosa! Ciertamente no estaba convencido de que fuera cierto de una manera férrea; Simplemente no pensé que fuera tan loco como la mayoría de la gente.

Pero estaba pensando fuera de la caja, pensando más allá de lo que le enseñaron. Si el cerebro realmente solo está asimilando y sintetizando información, ¿cómo se explican esos saltos?

Cómo lo hace nuestro cerebro, por supuesto que no tengo ni idea. Pero es claramente una habilidad de supervivencia útil. Es una de las cosas que ha hecho posible la sociedad humana. En algún momento alguien dijo: «Sabes, el fuego no es solo algo terrible que nos quema. Hace que la comida sea mejor».

¿Qué hay de Mozart escribiendo una sinfonía? Paraíso de las computadoras‘No he podido hacer algo así.

Bueno, han compuesto música. ¡No han compuesto nada que me gustaría escuchar! Pero los Mozart son muy raros. Como cualquier compositor, Mozart perfeccionó su oficio, y su cerebro de alguna manera se conectó de una manera muy especial que hizo que las ideas musicales se unieran. No tenemos idea de cómo sucedió eso. Ciertamente no sabemos cómo hacer Mozarts. Pero podríamos, algún día, saber cómo hacerlo.

Entonces crees que incluso eso sería posible.

No conozco ninguna razón por la que sea imposible. Esto conduce a la vieja cuestión de la mente y el cuerpo. Si le preguntaras a Kurt Gödel, diría que es ridículo pensar que el protoplasma está haciendo todo esto. Creía que la mente es algo abstracto que está más allá, que la mente hace uso del cerebro pero el cerebro no produce la mente. Por otro lado, Marvin Minsky dice que la mente es lo que hace el cerebro.

Los triunfos del 20^th La biología del siglo ha socavado el caso del vitalismo, que es la posición filosófica de que las propiedades de los seres vivos no pueden explicarse en términos de las leyes habituales de la física y la química. Gödel fue un vitalista con respecto a los fenómenos mentales, una visión que aún puede mantenerse coherentemente en el estado actual del conocimiento en neurociencia.

Allyn Jackson es un periodista especializado en ciencias y matemáticas que vive en Alemania.

entradas no encontradas