:For der Geiger, sieh Michael Rabin (Geiger).

Michael Oser Rabin (geboren am 1. September 1931), ist ein israelischer Computerwissenschaftler und ein Empfänger des Turing-Preises.

Lebensbeschreibung

Rabin ist 1931 in Breslau, Deutschland, (heute Wrocław, in Polen), der Sohn eines Rabbis geboren gewesen. 1935 ist er mit seiner Familie emigriert, um Palästina Zu beauftragen. Als ein junger Junge hat er sich sehr für die Mathematik interessiert, und sein Vater hat ihn an die beste Höhere Schule in Haifa gesandt, wo er unter einem bedeutenden sich übenden Mathematiker, Elisha Netanyahu studiert hat, der dann ein Lehrer der Höheren Schule war.

Nach der Höheren Schule wurde er in die Armee während 1948 arabisch-israelischer Krieg eingezogen. Der Mathematiker Abraham Fraenkel, der ein Professor der Mathematik in Jerusalem war, hat mit dem Armeebefehl dazwischengelegen, und Rabin wurde entlassen, um an der Universität 1949 zu studieren.

Er hat einen M.Sc. von der hebräischen Universität Jerusalems 1953 und eines Dr. von der Universität von Princeton 1956 erhalten.

Gegen Ende der 1950er Jahre wurde er seit einem Sommer eingeladen, um Forschung für IBM am Lamm-Stand in Westchester County, New York mit anderen viel versprechenden Mathematikern und Wissenschaftlern zu tun. Es war dort, dass er und Dana Scott das Papier "Begrenzte Automaten und Ihre Entscheidungsprobleme" geschrieben haben. Bald, mit nichtdeterministischen Automaten, sind sie im Stande gewesen, das Ergebnis von Kleene zu tadeln, dass Zustandsmaschinen genau regelmäßige Sprachen akzeptieren.

Betreffs der Ursprünge dessen, was rechenbetonte Kompliziertheitstheorie den nächsten Sommer werden sollte, ist Rabin zum Lamm-Stand zurückgekehrt. John McCarthy hat ein Rätsel zu ihm über Spione, Wächter und Kennwort aufgestellt, das Rabin studiert hat, und kurz nachdem er einen Artikel, "Grad der Schwierigkeit geschrieben hat, eine Funktion und Hierarchie von Rekursiven Sätzen Zu schätzen."

Nichtdeterministische Maschinen sind ein Schlüsselkonzept in der rechenbetonten Kompliziertheitstheorie, besonders mit der Beschreibung von Kompliziertheitsklassen P und NP geworden.

Rabin ist dann nach Jerusalem zurückgekehrt, Logik erforschend, und an den Fundamenten dessen arbeitend, was später als Informatik bekannt wäre. Er war ein Mitprofessor und der Leiter des Instituts für die Mathematik an der hebräischen Universität an 29 Jahren und ein voller Professor durch 33. Rückrufe von Rabin, "Gab es gar keine Anerkennung der Arbeit an den Problemen der Computerwissenschaft. Mathematiker haben das erscheinende neue Feld nicht anerkannt".

1960 wurde er von Edward F. Moore eingeladen, an Glockenlaboratorien zu arbeiten, wo Rabin probabilistic Automaten eingeführt hat, die Münzwerfen verwenden, um der Zustandübergänge zu entscheiden zu nehmen. Er hat Beispiele von regelmäßigen Sprachen gezeigt, die eine sehr hohe Zahl von Staaten verlangt haben, aber für den Sie die Exponentialverminderung der Zahl von Staaten bekommen, wenn Sie zu probabilistic Automaten durchgehen.

1969 hat Rabin bewiesen, dass die Theorie der zweiten Ordnung von n Nachfolgern entscheidbar ist. Ein Schlüsselbestandteil des Beweises hat implizit determinacy von Paritätsspielen gezeigt, die im dritten Niveau der Hierarchie von Borel liegen.

1975 hat Rabin seine Amtszeit als Rektor der hebräischen Universität Jerusalems beendet und ist zum Institut von Massachusetts für die Technologie in den USA als ein Gastprofessor gegangen. Gary Miller war auch dort und hatte seinen polynomischen Zeittest auf auf der verlängerten Hypothese von Riemann gestützten primality. Während dort Rabin den Müller-Rabin primality Test, ein randomized Algorithmus erfunden hat, der sehr schnell bestimmen kann (aber mit einer winzigen Wahrscheinlichkeit des Fehlers), ob eine Zahl erst ist. Die Methode von Rabin hat auf der vorherigen Arbeit von Gary Miller basiert, der das Problem deterministisch behoben hat in der Annahme, dass die verallgemeinerte Hypothese von Riemann die Version des wahren aber Rabins des Tests ist, hat keine solche Annahme gemacht. Schnelle Primality-Prüfung ist Schlüssel in der erfolgreichen Durchführung vom grössten Teil der Geheimschrift des öffentlichen Schlüssels, und 2003 Miller, Rabin, Robert M. Solovay, und Volker Strassen wurde Paris Kanellakis Preis für ihre Arbeit an der Primality-Prüfung gegeben.

1976 wurde er von Joseph Traub eingeladen, sich an der Universität von Carnegie Mellon zu treffen, und hat den Primality-Test präsentiert. Nachdem er diesen Vortrag gegeben hat, hatte Traub gesagt, "Nein, nein, das ist Revolutionär, und er dabei ist, sehr wichtig zu werden."

1979 hat Rabin den Rabin cryptosystem, den ersten asymmetrischen cryptosystem erfunden, dessen Sicherheit gleichwertig zur Hartnäckigkeit der ganzen Zahl factorization bewiesen wurde.

1981 hat Rabin eine schwache Variante der Technik der vergesslichen Übertragung wiedererfunden, die von Wiesner unter dem Namen davon erfunden ist, gleichzeitig zu senden, einem Absender erlaubend, eine Nachricht an einen Empfänger zu übersenden, wo der Empfänger etwas Wahrscheinlichkeit zwischen 0 und 1 hat, die Nachricht mit dem Absender zu erfahren, der nicht weiß, ob der Empfänger im Stande gewesen ist, so zu tun.

1987 hat Rabin, zusammen mit Richard Karp, einen der wohl bekanntesten effizienten Schnur-Suchalgorithmen, des Schnur-Suchalgorithmus von Rabin-Karp geschaffen, der für sein rollendes Kuddelmuddel bekannt ist.

Die neuere Forschung von Rabin hat sich auf die Computersicherheit konzentriert. Er ist zurzeit der Thomas J. Watson der Ältere. Professor der Informatik an der Universität von Harvard und Professor der Informatik an der hebräischen Universität. Während des Frühlingshalbjahres von 2007 war er ein Gastprofessor an der Universität von Columbia das Unterrichten der Einführung in die Geheimschrift.

Rabin ist ein ausländisches Mitglied der Nationalen USA-Akademie von Wissenschaften, ein Mitglied des

Französische Akademie von Wissenschaften und ein ausländisches Mitglied der Königlichen Gesellschaft.

Er war auch der Doktorberater von Saharon Shelah, einer der herausragenden energischen Forscher in der mathematischen Logik.

Preise

1976 wurde der Turing-Preis gemeinsam Rabin und Dana Scott für eine Zeitung geschrieben 1959, das Zitat zuerkannt, für die Staaten dass der Preis gewährt wurde:

Für ihr gemeinsames Papier "Begrenzte Automaten und Ihre Entscheidungsprobleme,", der die Idee von nichtdeterministischen Maschinen eingeführt hat, die sich erwiesen hat, ein enorm wertvolles Konzept zu sein. Ihr (Scott & Rabin) [sic] ist klassisches Papier eine dauernde Quelle der Inspiration für die nachfolgende Arbeit in diesem Feld gewesen.

1995 wurde Rabin dem Preis von Israel in Informatiken zuerkannt.

2010 wurde Rabin der Tel Aviver Universität Dan David Prize ("Zukünftige" Kategorie), gemeinsam mit Leonard Kleinrock und Gordon E. Moore, für Computer und Fernmeldewesen zuerkannt.

Siehe auch

• Vergessliche Übertragung
• Automat von Rabin
• Fingerabdruck von Rabin
• Hyperverschlüsselung
• Liste von Preis-Empfängern von Israel

Außenverbindungen

• Kurze Beschreibung in einer Informationswissenschaftsruhmeshalle an der Universität Pittsburghs

Vergessliche Übertragung

• Notierungen aus einigen von den Klassen von Professor Rabin
• Website für einen der Kurse von Rabin
• Beschreibung der Forschung von Rabin durch Richard J. Lipton