Die Natur ist unsere Quelle der Zufälligkeit: zum Tode von Michael O. Rabin

Michael O. Rabin wurde als Sohn des Rabbiners Israel Rabin und der Schriftstellerin Ester Rabin am 1. September 1931 in Breslau geboren. Die Familie wanderte 1935 in das britische Mandatsgebiet für Palästina aus. Sein mathematisches Interesse wurde durch seinen Lehrer Elisha Netanyahu mit der Aufnahme in einen kleinen Kreis interessierter Schüler gefördert. Als er mit 16 Jahren 1948 im israelisch-arabischen Krieg in die Armee eingezogen werden sollte, setzte sich der berühmte Mathematiker Abraham Fraenkel für seine weitere Ausbildung an der Universität ein. 1952 schloss Rabin das Studium mit einer Masterarbeit über ein von Emmy Noether entdecktes Problem ab, was ihm ein Stipendium an der Universität Princeton einbrachte. Dort studierte er zusammen mit Dana Scott bei Alonzo Church, bei dem auch Alan Turing studiert hatte.

Grundlegende Arbeiten

Rabin und Scott wurden im Sommer 1957 von IBM eingeladen und schrieben dort die Arbeit über „Finite Automata and Their Decision Problems“, in der sie sich mit den (heute so genannten) neuronalen Netzwerken von Warren McCulloch und Walter Pitts beschäftigten. 1956 hatte der Logiker Stephen Cole Kleene mit seinem Theorem die Klasse der regulären Sprachen in die Informatik eingeführt und deshalb konnten Rabin und Scott mit ihrer Arbeit über nichtdeterministische Automaten Kleenes Annahmen bestätigen. „Wir hatten eigentlich keinen tieferen philosophischen Grund, diesen Nichtdeterminismus in Betracht zu ziehen, obwohl er, wie wir heute wissen, im Zentrum der P = NP-Frage steht – einem Problem von immenser praktischer und theoretischer Bedeutung. Für uns war das lediglich eine von mehreren Varianten“, sagte Rabin im Interview über seinen Lebensweg, das er seinem Schüler Dennis Shasha gewährte. Im Jahre 1976 bekamen er und Scott für diese Arbeit den Turing Award, was bis heute Gegenstand von angeregten Diskussionen ist.

Nach dieser Episode beschäftigte sich Rabin mit kryptographischen Problemen, angeregt über ein Problem, das ihm John McCarthy gestellt hat: Wie kann ein Spion, der sein Passwort sagt, zuverlässig von einem Wächter erkannt werden, der das Passwort errechnen soll? Die Antwort war der Aufsatz „Probabilistic Algorithm for Testing Primality“ von Rabin. Der Primzahlentest, heute als Miller-Rabin-Test bekannt, liefert nach sechs Tests bei langen Zahlen schnell mit einer Wahrscheinlichkeit von 99,9 Prozent die Antwort auf die Frage, ob eine Zahl eine Primzahl ist und wird deshalb in vielen kryptografischen Anwendungen eingesetzt. Mit seinem Aufsatz „Digitalized Signatures and Public-Key Functions as Intractable as Factorization“ lieferte Rabin 1979 die Grundlagen für das Rabin-Kryptosystem, das im Gegensatz zum Primzahlentest kaum genutzt wird.

Später war Rabin nach jahrelanger Forschung und Lehre an der Hebrew University, deren Rektor er zeitweilig war, ab 1982 wieder bei IBM und gehörte dort bis 1994 zum Science Advisory Committee. 1987 entwickelte er mit Richard M. Karp den Rabin-Karp-Algorithmus, der bei der Suche nach Plagiaten mit einem effizienten Hash-Verfahren aufwartet. Im Interview über seinen Lebensweg schildert er, wie wichtig die Rolle des Zufalls für seine Arbeit gewesen ist. „Das Einwirken von Zufall bei so vielen algorithmischen Problemen ist mir völlig rätselhaft. Es ist effizient, es funktioniert; aber warum und wie, ist mir ein absolutes Rätsel. Algorithmen benötigen in ihrer Reinform eine physikalische Zufallsquelle. Es handelt sich also um eine Art Zusammenarbeit zwischen uns Informatikern und der Natur als Quelle des Zufalls. Das ist einzigartig und wirft einige Fragen in der Physik und Philosophie auf.“

(mho)