Michael Oser Rabin ( hebreo : מִיכָאֵל עוזר רַבִּין ; nacido el 1 de septiembre de 1931) es un matemático , informático y ganador del Premio Turing .
Rabin nació en 1931 en Breslavia , Alemania (hoy Wrocław , en Polonia ), hijo de un rabino . En 1935, emigró con su familia al Mandato Palestino . De 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 , que entonces era profesor de secundaria. [1]
Rabin se graduó en la Escuela Hebrea Reali de Haifa en 1948 y fue reclutado por 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 ante el mando del ejército y Rabin fue dado de baja para estudiar en la universidad en 1949. [1] Posteriormente, recibió una maestría en la Universidad Hebrea de Jerusalén . Comenzó sus estudios de posgrado en la Universidad de Pensilvania antes de recibir un doctorado en la Universidad de Princeton en 1956. [2]
Rabin se convirtió en profesor asociado de matemáticas en la Universidad de California, Berkeley (1961-1962) y en el MIT (1962-1963). Antes de trasladarse a la Universidad de Harvard como profesor Gordon McKay de informática en 1981, fue profesor en la Universidad Hebrea. [3]
A finales de los años 50, fue invitado a pasar un verano investigando para IBM en Lamb Estate, en el condado de Westchester, Nueva York, junto con otros matemáticos y científicos prometedores. Fue allí donde él y Dana Scott escribieron el artículo "Autómatas finitos y sus problemas de decisión". [4] Poco después, utilizando autómatas no deterministas, pudieron volver a demostrar el resultado de Kleene de que las máquinas de estados finitos aceptan exactamente los 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 acertijo sobre espías, guardias y contraseñas, que Rabin estudió y poco después escribió un artículo titulado "Grado de dificultad de calcular una función y jerarquía de conjuntos recursivos". [1] [5]
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 regresó a Jerusalén para investigar la lógica y trabajar en las bases de lo que más tarde se conocería como informática . A los 29 años era profesor asociado y director del Instituto de Matemáticas de la Universidad Hebrea, y a los 33 era profesor titular. Rabin recuerda: "No había ningún reconocimiento por el trabajo sobre cuestiones de informática. Los matemáticos no reconocían el nuevo campo emergente". [1]
En 1960, Edward F. Moore lo invitó a trabajar en los Laboratorios Bell , 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 1966 (publicado en actas de congresos en 1967), [6] Rabin introdujo la noción de tiempo polinomial (introducida independientemente y muy poco antes por Cobham [7] y Edmonds [8] ).
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 . [9] 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 los EE. UU. como profesor visitante. Mientras estaba 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 . [10] [11] 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 verdadera, pero la versión de la prueba de Rabin no hizo tal suposición. Las pruebas rápidas de primalidad son clave en la implementación exitosa de la mayoría 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 . [12]
En 1981, Rabin reinventó una variante débil de la técnica de transferencia inconsciente inventada por Wiesner bajo el nombre de multiplexación, [13] permitiendo a un emisor transmitir un mensaje a un receptor donde el receptor tiene una probabilidad entre 0 y 1 de aprender el mensaje, sin que el emisor sepa si el receptor fue capaz de hacerlo.
En 1987, Rabin, junto con Richard Karp , creó 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 continuo . [14]
Las investigaciones más recientes de Rabin se han centrado en la seguridad informática. Actualmente es profesor de informática de la cátedra Thomas J. Watson en la Universidad de Harvard y profesor de informática en la Universidad Hebrea . Durante el semestre de primavera de 2007, fue profesor visitante en la Universidad de Columbia, donde impartió la asignatura Introducción a la criptografía .
Rabin es miembro extranjero de la Academia Nacional de Ciencias de los Estados Unidos , [15] miembro de la Sociedad Filosófica Estadounidense , [16] miembro de la Academia Estadounidense de Artes y Ciencias , [17] 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 indica que el premio fue otorgado:
Por su artículo conjunto "Autómatas finitos y sus problemas de decisión", en el que se introdujo la idea de las 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. [18]
En 1995, Rabin recibió el Premio Israel , en ciencias de la computación. [19] 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. [20] Rabin recibió un Doctorado Honoris Causa en Ciencias de la Universidad de Harvard en 2017. [21]
Rabin tiene una hija, la científica informática Tal Rabin . [22]
{{cite journal}}: CS1 maint: URL no apta ( enlace )