Michael O. Rabin: O homem que tornou os computadores confortáveis com o acaso

Por volta dos dez ou onze anos, na Palestina sob mandato britânico, Michael Rabin resolveu um problema de geometria que havia deixado perplexos estudantes muito mais velhos que ele — um pequeno sinal precoce de uma mente que passaria o resto do século encontrando caminhos elegantes e inesperados através de problemas que todos os outros presumiam exigir certeza absoluta. O movimento característico de Rabin, repetido na teoria dos autômatos, na criptografia e na teoria dos números, foi notar que dar a uma máquina permissão para adivinhar, ou para lançar uma moeda, poderia torná-la mais poderosa em vez de menos confiável — uma ideia considerada quase herética quando ele a propôs pela primeira vez.

De Breslau a um lar rabínico na Palestina

Rabin nasceu em 1 de setembro de 1931, em Breslau, então na Alemanha e agora Wrocław, Polônia. Seu pai, um rabino, mudou a família para a Palestina em 1935, antes do pior do que estava por vir na Europa. Ele frequentou a Escola Hebraica Reali em Haifa, estudando sob a tutela do matemático Elisha Netanyahu, que mais tarde se tornou professor no Technion, e na adolescência já estava trabalhando em seminários de matemática avançada. Ele obteve um mestrado em matemática na Universidade Hebraica de Jerusalém em 1953, com uma tese que resolveu um problema em aberto originalmente proposto por Emmy Noether, antes de cruzar para os Estados Unidos para um doutorado em Princeton, concluído em 1957 sob a direção do lógico Alonzo Church.

Uma máquina que pode adivinhar

O primeiro artigo importante de Rabin, escrito com Dana Scott e publicado em 1959 como "Autômatos Finitos e Seus Problemas de Decisão", introduziu o conceito do autômato finito não determinístico — uma máquina teórica que, ao encontrar uma entrada, poderia efetivamente ramificar-se em múltiplas cópias de si mesma e seguir vários caminhos computacionais possíveis ao mesmo tempo. O artigo provou que essas máquinas não determinísticas eram, apesar de parecerem muito mais poderosas, exatamente equivalentes no que podiam calcular às determinísticas comuns, um resultado fundamental que reformulou a forma como a ciência da computação pensa sobre a própria computação. A Association for Computing Machinery concedeu a Rabin e Scott o Prêmio Turing em 1976 especificamente por esse artigo — a maior honra da ciência da computação, por uma peça de teoria escrita quando Rabin ainda não tinha trinta anos.

Ensinando o acaso a ser confiável

Rabin voltou repetidamente a uma ideia relacionada e mais estranha: que injetar deliberadamente aleatoriedade em um cálculo poderia torná-lo mais rápido ou mais simples, sem torná-lo indigno de confiança. Nos Laboratórios Bell, por volta de 1960, ele introduziu autômatos probabilísticos que usavam lançamentos de moeda para decidir transições de estado, mostrando que podiam representar certas linguagens com estados exponencialmente menores do que qualquer máquina determinística. Essa intuição amadureceu, em 1975, no teste de primalidade de Miller-Rabin, um algoritmo aleatorizado — baseando-se no trabalho determinístico anterior de Gary Miller — para determinar se um número enorme é primo, rápido e confiável o suficiente para sustentar sistemas de criptografia usados na Internet moderna; a versão de Rabin notavelmente removeu a dependência de Miller da hipótese de Riemann generalizada não provada. O Prêmio Kanellakis de 2003 reconheceu a contribuição compartilhada de Miller, Rabin, Robert Solovay e Volker Strassen para essa linha de trabalho.

Fechaduras construídas a partir de matemática difícil

A criptografia de Rabin foi além de testar números primos. Em 1978, ele criou o criptossistema de Rabin, notável por ser o primeiro esquema de criptografia assimétrica cuja segurança poderia ser provada matematicamente equivalente à dificuldade de fatorar grandes números inteiros — uma garantia mais forte do que a maioria dos criptossistemas da época poderia reivindicar. Em 1981, ele formalizou a transferência inconsciente, um protocolo criptográfico que permite que informações sejam enviadas de modo que o remetente não possa saber se o receptor realmente as obteve, o que se tornou um bloco de construção para a computação multipartidária segura. Em 1987, com Richard Karp, ele co-desenvolveu o algoritmo de busca de strings Rabin-Karp, uma técnica de hash rolante ainda ensinada em cursos de graduação de algoritmos por sua eficiência em encontrar um padrão dentro de um grande corpo de texto.

Uma carreira dividida entre dois países

A vida acadêmica de Rabin correu em trilhas paralelas entre Israel e os Estados Unidos. Na Universidade Hebraica de Jerusalém, ele subiu de professor assistente a professor titular no início dos seus trinta anos, presidiu seu Instituto de Matemática e serviu como reitor da universidade de 1972 a 1975. Nos Estados Unidos, ele ocupou a Cátedra Gordon McKay e depois a Cátedra Thomas J. Watson Sr. em Harvard a partir de 1981, juntamente com cargos de professor visitante no MIT, Berkeley e Columbia. Ele foi eleito para a Academia Nacional de Ciências dos EUA, a Academia Americana de Artes e Ciências, a Sociedade Filosófica Americana, a Academia Francesa de Ciências e a Royal Society, e ganhou o Prêmio Israel em 1995 e o Prêmio Dan David em 2010, além de honrarias incluindo o Prêmio IEEE Charles Babbage e o Prêmio Dijkstra.

Por que Michael é chamado de gênio

O caso de Rabin como gênio baseia-se em uma assinatura reconhecível ao longo de uma carreira de cinquenta anos: identificar repetidamente que um problema que se presumia exigir certeza poderia, em vez disso, ser resolvido mais rapidamente, ou tornado mais poderoso, ao introduzir deliberadamente aleatoriedade ou não determinismo — uma percepção que a princípio chocou os contemporâneos como um erro de categoria, já que a aleatoriedade era amplamente tratada como o inimigo da computação confiável, e não como um recurso para ela. Essa percepção, aplicada independentemente à teoria dos autômatos, testes de primalidade e design de protocolos criptográficos, produziu resultados que, cada um por si só, marcariam uma carreira substancial; produzir vários é o que o comitê do Prêmio Turing e a série de prêmios posteriores Kanellakis, Babbage e Dijkstra estavam honrando explicitamente. Há poucos contra-argumentos sérios no registro: ao contrário de alguns laureados com o Turing cujas reputações repousam em um único artigo, a de Rabin é construída sobre resultados verificados independentemente e ainda usados ao longo de décadas — o teste de Miller-Rabin roda hoje dentro de bibliotecas criptográficas, não apenas em livros didáticos. Se há uma ressalva, é apenas que seu artigo individual mais famoso, com Scott, veio de uma parceria genuína, um lembrete de que até mesmo a percepção individual mais aguçada neste campo geralmente chegou através da colaboração, e não do gênio solitário.

Legado

Rabin faleceu em 14 de abril de 2026, aos noventa e quatro anos, tendo passado seus últimos anos ainda associado tanto a Harvard quanto à Universidade Hebraica como professor emérito em cada uma. Sua filha, Tal Rabin, tornou-se uma distinta criptógrafa por mérito próprio, levando a fascinação particular da família pelo acaso e pelo segredo para uma nova geração. Os algoritmos que levam seu nome — Miller-Rabin, Rabin-Karp, o criptossistema de Rabin — permanecem em uso ativo e diário onde quer que um computador precise testar um número, pesquisar uma string ou manter um segredo, um caso raro de ciência da computação teórica fundamental que ainda realiza um trabalho diário visível décadas depois de ter sido escrito.