
Michael Oser Rabin
Informático israelí de origen alemán, uno de los creadores de la teoría de la complejidad computacional y ganador del Premio Turing de 1976 · 1931–2026
- Nacimiento
- 1 de septiembre de 1931
- Fallecimiento
- 14 de abril de 2026
- País
- Israel
- Sección
- Informática
- Premios
- Premio Turing
Biografía
Michael Oser Rabin (Breslau, 1 de septiembre de 1931 – 14 de abril de 2026) fue un informático de origen israelí y nacionalidad estadounidense cuyo trabajo sentó bases de la teoría de la complejidad, la disciplina que estudia cuánto esfuerzo exige resolver cada problema. En 1976 compartió con Dana Scott el Premio Turing, el reconocimiento más prestigioso de la informática. Sus investigaciones, desarrolladas entre los años cincuenta y ochenta, dieron lugar a herramientas que hoy sostienen la criptografía y la programación modernas.
Nació en Breslau, en la Alemania de entonces, hoy Wrocław, en Polonia, y era hijo de un rabino. En 1935 emigró con su familia al Mandato Británico de Palestina. Estudió en un instituto de Haifa, donde tuvo como profesor al matemático Elisha Netanyahu, y al terminar el bachillerato en 1948 fue reclutado durante la guerra árabe-israelí. El matemático Abraham Fraenkel intercedió ante el mando militar, y Rabin fue dado de baja para continuar sus estudios en la universidad en 1949. Obtuvo el máster en la Universidad Hebrea de Jerusalén en 1953, cursó estudios de doctorado en la Universidad de Pensilvania y se doctoró en la Universidad de Princeton en 1956.
A finales de los cincuenta, IBM invitó a varios matemáticos y científicos prometedores a pasar un verano investigando en una antigua finca de Westchester, en el estado de Nueva York. Allí Rabin escribió con Dana Scott el artículo «Finite Automata and Their Decision Problems». Un autómata finito es un modelo abstracto de máquina con un número limitado de estados. Los dos autores introdujeron las máquinas no deterministas, que pueden seguir varios caminos a la vez y aceptar una secuencia si alguno de ellos llega a un final válido. Con esta herramienta volvieron a demostrar un resultado previo de Kleene sobre los lenguajes que reconocen estas máquinas.
El verano siguiente regresó a la finca. John McCarthy le planteó un acertijo sobre espías, guardias y contraseñas, que llevó a Rabin a preguntarse cuánto cuesta calcular una función. De ese trabajo surgió un artículo sobre la dificultad de computar funciones y la jerarquía de conjuntos recursivos, que se considera uno de los orígenes de la teoría de la complejidad. Las máquinas no deterministas resultaron clave para describir las clases P y NP, es decir, los problemas que pueden resolverse con rapidez y los que solo pueden comprobarse con rapidez. Según relató el propio Rabin, los matemáticos de la época no apreciaban aún el valor de este campo emergente.
Tras volver a Jerusalén, fue profesor asociado a los 29 años y catedrático a los 33. En 1960 Edward F. Moore le invitó a trabajar en Bell Labs, donde presentó los autómatas probabilísticos, máquinas que usan lanzamientos de moneda para decidir qué transición seguir. En algunos casos estas máquinas necesitaban exponencialmente menos estados que las deterministas. En 1966 planteó la noción de tiempo polinómico, que describe los problemas cuyo tiempo de resolución crece de forma manejable con el tamaño de la entrada, idea que surgió casi al mismo tiempo en el trabajo de Cobham y Edmonds. Pasó temporadas en Berkeley y en el MIT, y en 1981 se trasladó a Harvard.
Su aportación más usada en la práctica es el test de Miller-Rabin, que ideó en 1975 mientras estaba en el MIT. Permite comprobar si un número es primo con gran rapidez y con una probabilidad de error diminuta. Se apoyaba en un trabajo previo de Gary Miller, que resolvía el problema de forma determinista solo si se aceptaba la hipótesis de Riemann generalizada, una conjetura matemática no demostrada; la versión de Rabin no necesitaba esa suposición. En 2003 Miller, Rabin, Robert Solovay y Volker Strassen recibieron el premio Paris Kanellakis por su trabajo sobre primalidad. Hacia 1979 creó el criptosistema Rabin, el primero de clave asimétrica cuya seguridad quedó demostrada equivalente a la dificultad de factorizar números enteros grandes. En 1981 reinventó una versión débil de la transferencia inconsciente, una técnica ideada por Wiesner con el nombre de multiplexación, y en 1987, junto a Richard Karp, creó el algoritmo de búsqueda de cadenas Rabin-Karp, que emplea una función hash deslizante.
Sus últimas investigaciones se centraron en la seguridad informática. En 2007 impartió en la Universidad de Columbia un curso de introducción a la criptografía. Se retiró como profesor emérito de Harvard y de la Universidad Hebrea. Fue miembro extranjero de la Academia Nacional de Ciencias de Estados Unidos y de la Royal Society británica, y recibió el Premio Israel en 1995. Su legado se encuentra en el vocabulario de la complejidad computacional y en algoritmos que protegen buena parte de las comunicaciones cotidianas. Su hija, Tal Rabin, es también una destacada informática.
Aportaciones principales
- 1959Autómatas finitos y su problema de decisión, escrito con Dana Scott, donde se introducen las máquinas no deterministas, base de la teoría de la complejidad.
- 1960Autómatas probabilísticos, máquinas que usan el azar para elegir sus transiciones y que a veces necesitan muchos menos estados.
- 1966Noción de tiempo polinómico, que mide si el tiempo de resolución de un problema crece de forma manejable.
- 1975Test de primalidad de Miller-Rabin, un método aleatorio que comprueba muy rápido si un número es primo.
- 1979Criptosistema Rabin, el primero de clave asimétrica cuya seguridad equivale a la dificultad de factorizar enteros.
- 1981Versión débil de la transferencia inconsciente, que permite enviar un mensaje sin que el emisor sepa si el receptor lo ha recibido.
- 1987Algoritmo de búsqueda de cadenas Rabin-Karp, conocido por su función hash deslizante.
Maestros y alumnos
Aprendió de:
Formó a:
Curiosidades y anécdotas
Un acertijo de espías
Un juego sobre espías, guardias y contraseñas que le propuso John McCarthy acabó abriendo la puerta a la teoría de la complejidad.
Liberado del ejército
Reclutado en plena guerra de 1948, logró salir del ejército gracias a la intervención del matemático Abraham Fraenkel, que quería que siguiera estudiando.
Una familia de informáticos
Su hija, Tal Rabin, también es una reconocida informática.
Descubrimientos e inventos relacionados
- 1987Algoritmo Karp-RabinAlgoritmo que busca un patrón de caracteres dentro de un texto comparando primero firmas numéricas (funciones hash) y verificando letra a letra solo cuando coinciden.
Sus contemporáneos
Mientras vivía Michael Oser Rabin (1931–2026)…
Vivieron a la vez
Se descubrió o inventó en esos años
- 1931Big BangModelo cosmológico que describe cómo el universo se expandió desde un estado inicial de densidad y temperatura extremas, hace unos 13 800 millones de años.
- 1932NeutrónPartícula subatómica sin carga eléctrica neta, presente en el núcleo de casi todos los átomos junto con los protones.
- 1945ComputadoraMáquina programable que recibe datos, los procesa siguiendo instrucciones y entrega resultados, con una arquitectura de hardware y software que puede cambiar de tarea sin cambiar de cuerpo.
- 1969InternetRed mundial de redes de ordenadores interconectadas que se comunican mediante el conjunto de protocolos TCP/IP.
- 1973Teléfono móvilDispositivo electrónico portátil que permite hacer llamadas por radiofrecuencia mientras el usuario se desplaza dentro de la zona de cobertura de una red.
- 1989World Wide WebSistema de documentos y recursos interconectados por enlaces (hipervínculos) y accesibles a través de Internet mediante navegadores web.
Edsger Dijkstra1930–2002 · Informática
Dana Scott1932 · Informática
John Hopfield1933 · Informática
Niklaus Wirth1934–2024 · Informática
C. A. R. Hoare1934–2026 · Informática
Peter Naur1928–2016 · Informática