Martín Davis (matemático)

Martin David Davis (Marzo 8, 1928 – 1 de enero de 2023) fue un matemático americano y científico informático que contribuyó a los campos de la teoría de la computabilidad y la lógica matemática. Su trabajo sobre el décimo problema de Hilbert llevó al teorema MRDP. También avanzó el modelo Post-Turing y codesarrolló el algoritmo Davis–Putnam–Logemann–Loveland (DPLL), que es fundamental para los solversadores de satisfizo booles.

Davis ganó el Premio Leroy P. Steele, el Premio Chauvenet (con Reuben Hersh), y el Premio Lester R. Ford. Era miembro de la American Academy of Arts and Sciences y miembro de la American Mathematical Society.

Vida temprana y educación

Los padres de Davis eran inmigrantes judíos de Łódź, Polonia, que llegaron a los Estados Unidos y se casaron después de volver a encontrarse en la ciudad de Nueva York. Davis nació en la ciudad de Nueva York el 8 de marzo de 1928. Creció en el Bronx, donde sus padres lo alentaron a obtener una educación completa. Se graduó en la prestigiosa Escuela Secundaria de Ciencias del Bronx en 1944 y recibió su licenciatura en matemáticas en el City College en 1948 y su doctorado en la Universidad de Princeton en 1950. Su tesis doctoral, titulada Sobre la Teoría de la insolvabilidad recursiva, fue supervisada por el matemático e informático estadounidense Alonzo Church.

Carrera académica

Durante una estancia como instructor de investigación en la Universidad de Illinois en Urbana-Champaign a principios de la década de 1950, se unió al Laboratorio de sistemas de control y se convirtió en uno de los primeros programadores de ORDVAC. Posteriormente trabajó en Bell Labs y RAND Corporation antes de unirse a la Universidad de Nueva York. Durante su estancia en la Universidad de Nueva York, ayudó a establecer el departamento de informática de la universidad. Se retiró de la Universidad de Nueva York en 1996. Posteriormente fue miembro del profesorado visitante de la Universidad de California, Berkeley.

Décimo problema de Hilbert

Davis trabajó por primera vez en el décimo problema de Hilbert durante su tesis doctoral, en colaboración con Alonzo Church. El teorema, planteado por el matemático alemán David Hilbert, plantea una pregunta: dada una ecuación diofántica, ¿existe un algoritmo que pueda decidir si la ecuación tiene solución? La disertación de Davis planteó la conjetura de que el problema era irresoluble. En las décadas de 1950 y 1960, Davis, junto con las matemáticas estadounidenses Hilary Putnam y Julia Robinson, avanzaron hacia la resolución de esta conjetura. La demostración de la conjetura se completó finalmente en 1970 con el trabajo del matemático ruso Yuri Matiyasevich. Esto resultó en el teorema MRDP o DPRM, llamado así en honor a Davis, Putnam, Robinson y Matiyasevich. Al describir el problema, Davis había mencionado anteriormente que lo encontraba "irresistiblemente seductor". cuando era estudiante y más tarde se había convertido progresivamente en su "obsesión de toda la vida".

Otras contribuciones

Davis colaboró con Putnam, George Logemann y Donald W. Loveland en 1961 para presentar el algoritmo Davis-Putnam-Logemann-Loveland (DPLL), que era un algoritmo de búsqueda completo basado en el retroceso para decidir la satisfacibilidad de la lógica proposicional. fórmulas en forma normal conjuntiva, es decir, para resolver el problema CNF-SAT. El algoritmo fue un refinamiento del anterior algoritmo de Davis-Putnam, que era un procedimiento basado en resolución desarrollado por Davis y Putnam en 1960. El algoritmo es fundamental en la arquitectura de los solucionadores rápidos de satisfacibilidad booleana.

Además de su trabajo sobre la teoría de la computabilidad, Davis también hizo importantes contribuciones a los campos de la complejidad computacional y la lógica matemática. Davis también era conocido por su modelo de máquinas Post-Turing.

En 1974, Davis ganó el premio Lester R. Ford por sus escritos expositivos relacionados con su trabajo sobre el décimo problema de Hilbert, y en 1975 ganó el premio Leroy P. Steele y el premio Chauvenet (con Reuben Hersh). ). Se convirtió en miembro de la Academia Estadounidense de Artes y Ciencias en 1982 y, en 2013, fue seleccionado como uno de los miembros inaugurales de la Sociedad Estadounidense de Matemáticas.

El libro de Davis de 1958 Computability and Unsolvability se considera un clásico de la informática teórica, mientras que su libro de 2000 The Universal Computer rastrea la evolución y la historia de la informática. empezando por incluir obras de Gottfried Wilhelm Leibniz y Alan Turing. Su libro Lo indecidible, cuya primera edición se publicó en 1965, era una colección de problemas irresolubles y funciones computables.

Vida y muerte personal

Davis estaba casado con Virginia Whiteford Palmer, una artista textil. La pareja se conoció durante su estancia en el área de Urbana-Champaign y posteriormente se casó en 1951. Tuvieron dos hijos. La pareja vivió en Berkeley, California, después de su jubilación.

Davis murió el 1 de enero de 2023, a los 94 años. Su esposa murió el mismo día, varias horas después.

Publicaciones seleccionadas

Libros

• Davis, Martin (1958). Computación e insolvabilidad. Nueva York: Dover. ISBN 0-486-61471-9. 1982 Reimpresión de Dover
• Davis, Martin (1977). Análisis no estándar aplicado. Wiley. ISBN 9780471198970. 2014 Reimpresión de Dover
• Davis, Martin; Weyuker, Elaine J.; Sigal, Ron (1994). Computación, complejidad e idiomas: fundamentales de la ciencia informática teórica (2a edición). Boston: Académica, Harcourt, Brace. ISBN 9780122063824.
• Davis, Martin (2000). The Universal Computer: The Road from Leibniz to Turing. Norton. ISBN 0393047857. Reimpreso como Motores de lógica: Matemáticos y el origen de la computadora. Nueva York: Norton. 2000. ISBN 9780393322293.
• Davis, Martin (2004). The Undecidable: Documentos básicos sobre proposiciones indecidables, problemas insolvables y funciones computables. Nueva York: Dover Publications. ISBN 0-486-43228-9 OCLC 53840050.

Artículos

• Davis, Martin (1973), "El décimo problema de Hilbert es insolvable", American Mathematical Monthly, 80(3), 233–269. doi:10.1080/00029890.1973.11993265.
• Davis, Martin (1995), "¿Es la visión matemática algorítmica?", Behavioral and Brain Sciences, 13(4), 659-60.
• Davis, Martin (2020), "Seventy Years of Computer Science", En: Blass A., Cégielski P., Dershowitz N., Droste M., Finkbeiner B. (eds.) Campos de lógica y computación III, 105-117. Conference Notes in Computer Science, vol. 12180. Springer: Cham, Suiza. doi:10.1007/978-3-030-48006-6_8.