מייקל רבין: האיש שהפך מחשבים לנינוחים עם הסתברות
בגיל עשר או אחת-עשרה, בארץ ישראל בתקופת המנדט, פתר מייקל רבין בעיה גיאומטרית שהביכה תלמידים מבוגרים ממנו בשנים — סימן מוקדם וקטן למוח שיבלה את שארית המאה במציאת נתיבים אלגנטיים ובלתי צפויים לבעיות שכולם הניחו כי הן דורשות ודאות מוחלטת. המהלך המזוהה עם רבין, שחזר על עצמו בתורת האוטומטים, בקריפטוגרפיה ובתורת המספרים, היה ההבחנה שמתן רשות למכונה לנחש, או להטיל מטבע, יכול להפוך אותה לחזקה יותר ולא לפחות אמינה — רעיון שנחשב כמעט לכפירה כאשר הציע אותו לראשונה.
מברסלאו למשק בית של רב בארץ ישראל
רבין נולד ב-1 בספטמבר 1931 בברסלאו, אז בגרמניה וכיום ורוצלב, פולין. אביו, שהיה רב, העביר את המשפחה לארץ ישראל ב-1935, לפני שהחמיר המצב באירופה. הוא למד בבית הספר הריאלי העברי בחיפה, תחת המתמטיקאי אלישע נתניהו, שמאוחר יותר הפך לפרופסור בטכניון, וכבר בשנות נעוריו עבד בסמינרים למתמטיקה מתקדמת. הוא השלים תואר שני במתמטיקה באוניברסיטה העברית בירושלים ב-1953, בתזה שפתרה בעיה פתוחה שהציבה במקור אמי נתר (Emmy Noether), לפני שעבר לארצות הברית לדוקטורט בפרינסטון, אותו השלים ב-1957 תחת הלוגיקן אלונזו צ'רץ' (Alonzo Church).
מכונה שיכולה לנחש
המאמר המוקדם המשמעותי ביותר של רבין, שנכתב עם דנה סקוט (Dana Scott) ופורסם ב-1959 תחת הכותרת "Finite Automata and Their Decision Problems", הציג את המושג של אוטומט סופי לא-דטרמיניסטי — מכונה תיאורטית שעם קבלת קלט, יכולה למעשה להתפצל למספר עותקים של עצמה ולעקוב אחר מספר נתיבי חישוב אפשריים בו-זמנית. המאמר הוכיח שמכונות לא-דטרמיניסטיות אלו, למרות שנראו חזקות בהרבה, שקולות לחלוטין במה שהן יכולות לחשב למכונות דטרמיניסטיות רגילות, תוצאת יסוד שעיצבה מחדש את האופן שבו מדעי המחשב תופסים את החישוב עצמו. האגודה למכונות מחשוב (ACM) העניקה לרבין ולסקוט את פרס טיורינג ב-1976 בדיוק עבור מאמר זה — הכבוד הגבוה ביותר במדעי המחשב, עבור יצירה תיאורטית שנכתבה כשמייקל רבין טרם היה בן שלושים.
Twenty questions, eight minutes on the clock, and a percentile measured against everyone who has taken it. No sign-up.
Take the IQ test →ללמד את ההסתברות להיות אמינה
רבין חזר שוב ושוב לרעיון קשור ומוזר יותר: שהחדרת אקראיות לחישוב באופן מכוון יכולה להפוך אותו למהיר או פשוט יותר, מבלי להפוך אותו לבלתי אמין. במעבדות בל (Bell Labs) בסביבות שנת 1960 הוא הציג אוטומטים הסתברותיים שהשתמשו בהטלות מטבע כדי להחליט על מעברי מצבים, והראה שהם יכולים לייצג שפות מסוימות עם מספר מצבים קטן אקספוננציאלית מכל מכונה דטרמיניסטית. אינטואיציה זו הבשילה, בשנת 1975, לבדיקת הראשוניות מילר-רבין (Miller-Rabin), אלגוריתם אקראי — המתבסס על עבודה דטרמיניסטית קודמת של גארי מילר (Gary Miller) — לקביעה האם מספר עצום הוא ראשוני, מהירה ואמינה מספיק כדי לעמוד בבסיס מערכות הצפנה המשמשות את האינטרנט המודרני; הגרסה של רבין הסירה באופן בולט את התלות של מילר בהשערת רימן המוכללת שלא הוכחה. פרס קנלאקיס (Kanellakis Award) לשנת 2003 הכיר בתרומה המשותפת של מילר, רבין, רוברט סולוביי (Robert Solovay) ופולקר שטראסן (Volker Strassen) לקו עבודה זה.
מנעולים שנבנו ממתמטיקה קשה
הקריפטוגרפיה של רבין חרגה מעבר לבדיקת מספרים ראשוניים. בשנת 1978 הוא הגה את מערכת ההצפנה של רבין (Rabin cryptosystem), הראויה לציון כשיטת ההצפנה הא-סימטרית הראשונה שהאבטחה שלה הוכחה כמתמטית שקולה לקושי בפירוק לגורמים של מספרים שלמים גדולים — ערובה חזקה יותר ממה שרוב מערכות ההצפנה של התקופה יכלו לתבוע. בשנת 1981 הוא פורמליז את העברת המידע האובליביוזית (oblivious transfer), פרוטוקול קריפטוגרפי המאפשר שליחת מידע כך שהשולח אינו יכול לדעת אם המקבל אכן קיבל אותו, שהפך לאבן בניין לחישוב מאובטח מרובה משתתפים. בשנת 1987, יחד עם ריצ'רד קארפ (Richard Karp), הוא פיתח במשותף את אלגוריתם חיפוש המחרוזות רבין-קארפ (Rabin-Karp), טכניקת גיבוב מתגלגל שנלמדת עדיין בקורסי אלגוריתמים לתואר ראשון בשל יעילותה במציאת דפוס בתוך גוף טקסט גדול.
קריירה חצויה בין שתי מדינות
חייו האקדמיים של רבין התנהלו במסלולים מקבילים בין ישראל לארצות הברית. באוניברסיטה העברית בירושלים הוא עלה מדרגת מרצה בכיר לפרופסור מן המניין כבר בתחילת שנות השלושים לחייו, עמד בראש המכון למתמטיקה שלה, וכיהן כרקטור האוניברסיטה בין השנים 1972 ל-1975. בארצות הברית הוא החזיק בקתדרת גורדון מקיי (Gordon McKay Professorship) ולאחר מכן בקתדרת תומאס ג'יי ווטסון האב (Thomas J. Watson Sr. Professorship) באוניברסיטת הרווארד החל מ-1981, לצד מינויים אורחים ב-MIT, בברקלי ובקולומביה. הוא נבחר לאקדמיה הלאומית למדעים של ארה"ב, לאקדמיה האמריקאית לאמנויות ולמדעים, לחברה הפילוסופית האמריקאית, לאקדמיה הצרפתית למדעים ולחברה המלכותית הבריטית, וזכה בפרס ישראל בשנת 1995 ובפרס דן דוד בשנת 2010, לצד כיבודים הכוללים את פרס IEEE צ'ארלס בבג' (Charles Babbage Award) ופרס דייקסטרה (Dijkstra Prize).
מדוע מייקל מכונה גאון
המקרה של רבין כגאון נשען על חתימה ניתנת לזיהוי לאורך קריירה של חמישים שנה: זיהוי חוזר ונשנה של בעיה שהונח כי היא דורשת ודאות, וניתן היה לפתור אותה מהר יותר, או להפוך אותה לחזקה יותר, על ידי החדרת אקראיות או אי-דטרמיניזם במכוון — תובנה שבתחילה הכתה את בני דורו כטעות סיווג כמעט, שכן אקראיות נתפסה במידה רחבה כאויבת של חישוב אמין ולא כמשאב עבורו. אותה תובנה, שיושמה באופן עצמאי על תורת האוטומטים, בדיקת ראשוניות ועיצוב פרוטוקולים קריפטוגרפיים, הניבה תוצאות שכל אחת מהן לבדה הייתה מסמנת קריירה משמעותית; ייצורן של מספר תוצאות כאלו הוא מה שוועדת פרס טיורינג ורצף פרסי קנלאקיס, בבג' ודייקסטרה המאוחרים יותר כיבדו במפורש. אין כמעט טיעון נגד רציני בתיעוד: בניגוד לחלק מחתני פרס טיורינג שהמוניטין שלהם נשען על מאמר אחד, המוניטין של רבין בנוי על תוצאות מאומתות באופן עצמאי שעדיין נמצאות בשימוש במשך עשורים — מבחן מילר-רבין רץ בתוך ספריות קריפטוגרפיות כיום, לא רק בספרי לימוד. אם יש סייג, הוא רק שהמאמר הבודד המפורסם ביותר שלו, עם סקוט, הגיע משותפות אמיתית, תזכורת לכך שאפילו התובנה האישית החדה ביותר בתחום זה הגיעה בדרך כלל דרך שיתוף פעולה ולא דרך גאונות בודדת.
מורשת
רבין נפטר ב-14 באפריל 2026, בגיל תשעים וארבע, לאחר שבילה את שנותיו האחרונות עדיין בקשר עם הרווארד ועם האוניברסיטה העברית כפרופסור אמריטוס בשתיהן. בתו, טל רבין, הפכה לקריפטוגרפית מכובדת בזכות עצמה, כשהיא נושאת את הקסם המיוחד של המשפחה מאקראיות וסודיות לדור חדש. האלגוריתמים הנושאים את שמו — מילר-רבין, רבין-קארפ, מערכת ההצפנה של רבין — נותרו בשימוש פעיל ויומיומי בכל מקום שבו מחשב צריך לבדוק מספר, לחפש מחרוזת או לשמור סוד, מקרה נדיר של מדעי מחשב תיאורטיים יסודיים שעושים עדיין עבודה יומיומית גלויה עשורים לאחר שנכתבו.