Michael Oser Rabin ( hebreo : מִיכָאֵל עוזר רַבִּין ; nacido el 1 de septiembre de 1931) es un matemático , informático y ganador del Premio Turing israelí .
Rabin nació en 1931 en Breslau , Alemania (hoy Wrocław , en Polonia ), hijo de un rabino . En 1935 emigró con su familia al Mandato Palestina . Cuando era niño, estaba muy interesado en las matemáticas y su padre lo envió a la mejor escuela secundaria de Haifa , donde estudió con el matemático Elisha Netanyahu , quien entonces era profesor de secundaria. [1]
Rabin se graduó de la Escuela Hebrea Reali en Haifa en 1948 y fue reclutado en el ejército durante la Guerra Árabe-Israelí de 1948 . El matemático Abraham Fraenkel , que era profesor de matemáticas en Jerusalén , intervino en el mando del ejército y Rabin fue dado de alta para estudiar en la universidad en 1949. [1] Posteriormente, recibió una maestría en ciencias de la Universidad Hebrea de Jerusalén . Comenzó estudios de posgrado en la Universidad de Pensilvania antes de recibir un doctorado. de la Universidad de Princeton en 1956. [2]
Rabin se convirtió en profesor asociado de matemáticas en la Universidad de California, Berkeley (1961–62) y el MIT (1962–63). Antes de trasladarse a la Universidad de Harvard como profesor Gordon McKay de Ciencias de la Computación en 1981, fue profesor en la Universidad Hebrea. [3]
A finales de la década de 1950, lo invitaron a pasar un verano para realizar investigaciones para IBM en Lamb Estate en el condado de Westchester, Nueva York, con otros matemáticos y científicos prometedores. Fue allí donde él y Dana Scott escribieron el artículo "Finite Automata and Their Decision Problems". [4] Pronto, utilizando autómatas no deterministas, pudieron volver a probar el resultado de Kleene de que las máquinas de estados finitos aceptan exactamente lenguajes regulares. [1]
En cuanto a los orígenes de lo que se convertiría en la teoría de la complejidad computacional , el verano siguiente Rabin regresó a Lamb Estate. John McCarthy le planteó un enigma sobre espías, guardias y contraseñas, que Rabin estudió y poco después escribió un artículo, "Grado de dificultad de calcular una función y jerarquía de conjuntos recursivos". [ 15]
Las máquinas no deterministas se han convertido en un concepto clave en la teoría de la complejidad computacional, particularmente con la descripción de las clases de complejidad P y NP .
Rabin luego regresó a Jerusalén, investigando la lógica y trabajando en los fundamentos de lo que más tarde se conocería como ciencias de la computación . Era profesor asociado y director del Instituto de Matemáticas de la Universidad Hebrea a los 29 años, y profesor titular a los 33. Rabin recuerda: "No se valoraba en absoluto el trabajo sobre cuestiones de informática. Los matemáticos no reconocer el nuevo campo emergente". [1]
En 1960, Edward F. Moore lo invitó a trabajar en Bell Labs , donde Rabin introdujo autómatas probabilísticos que emplean lanzamientos de monedas para decidir qué transiciones de estado tomar. Mostró ejemplos de lenguajes regulares que requerían una gran cantidad de estados, pero para los cuales se obtiene una reducción exponencial del número de estados con autómatas probabilísticos. [1]
En 1969, Rabin introdujo los autómatas de árbol infinito y demostró que la teoría monádica de segundo orden de n sucesores ( S2S cuando n = 2) es decidible . [6] Un componente clave de la prueba mostró implícitamente la determinación de los juegos de paridad , que se encuentran en el tercer nivel de la jerarquía de Borel .
En 1975, Rabin terminó su mandato como rector de la Universidad Hebrea de Jerusalén y fue al Instituto Tecnológico de Massachusetts en Estados Unidos como profesor invitado. Mientras estuvo allí, Rabin inventó la prueba de primalidad de Miller-Rabin , un algoritmo aleatorio que puede determinar muy rápidamente (pero con una pequeña probabilidad de error) si un número es primo . [7] [8] El método de Rabin se basó en el trabajo previo de Gary Miller que resolvió el problema de manera determinista con el supuesto de que la hipótesis generalizada de Riemann es cierta, pero la versión de Rabin de la prueba no hacía tal supuesto. Las pruebas rápidas de primalidad son clave para la implementación exitosa de la mayor parte de la criptografía de clave pública, y en 2003 Miller, Rabin, Robert M. Solovay y Volker Strassen recibieron el premio Paris Kanellakis por su trabajo en pruebas de primalidad.
En 1976, Joseph Traub lo invitó a reunirse en la Universidad Carnegie Mellon y presentó la prueba de primalidad, que Traub calificó de "revolucionaria". [1]
En 1979, Rabin inventó el criptosistema Rabin , el primer criptosistema asimétrico cuya seguridad demostró ser equivalente a la intratabilidad de la factorización de números enteros . [9]
En 1981, Rabin reinventó una variante débil de la técnica de transferencia ajena inventada por Wiesner con el nombre de multiplexación, [10] permitiendo a un remitente transmitir un mensaje a un receptor donde el receptor tiene alguna probabilidad entre 0 y 1 de aprender el mensaje. , sin que el remitente sepa si el receptor pudo hacerlo.
En 1987, Rabin, junto con Richard Karp , crearon uno de los algoritmos de búsqueda de cadenas eficientes más conocidos , el algoritmo de búsqueda de cadenas Rabin-Karp , conocido por su hash rodante . [11]
La investigación más reciente de Rabin se ha centrado en la seguridad informática. Actualmente es profesor Thomas J. Watson Sr. de Ciencias de la Computación en la Universidad de Harvard y profesor de Ciencias de la Computación en la Universidad Hebrea . Durante el semestre de primavera de 2007, fue profesor visitante en la Universidad de Columbia enseñando Introducción a la Criptografía .
Rabin es miembro extranjero de la Academia Nacional de Ciencias de los Estados Unidos , [12] miembro de la Sociedad Filosófica Estadounidense , [13] miembro de la Academia Estadounidense de Artes y Ciencias , [14] miembro de la Academia Francesa de Ciencias y miembro extranjero de la Royal Society .
En 1976, el Premio Turing fue otorgado conjuntamente a Rabin y Dana Scott por un artículo escrito en 1959, cuya cita establece que el premio fue otorgado:
Por su artículo conjunto "Finite Automata and Their Decision Problems", que introdujo la idea de máquinas no deterministas, que ha demostrado ser un concepto enormemente valioso. Su artículo clásico (Scott & Rabin) [ sic ] ha sido una fuente continua de inspiración para trabajos posteriores en este campo. [15]
En 1995, Rabin recibió el Premio Israel en informática. [16] En 2010, Rabin recibió el Premio Dan David de la Universidad de Tel Aviv (categoría "Futuro"), junto con Leonard Kleinrock y Gordon E. Moore , por Computadoras y Telecomunicaciones. [17] Rabin recibió el título de Doctor Honoris Causa en Ciencias de la Universidad de Harvard en 2017. [18]
Rabin tiene una hija, la informática Tal Rabin . [19]
{{cite journal}}: Mantenimiento CS1: URL no apta ( enlace )