マイケル・ラビン

この項目では、計算機科学者のマイケル・ラビンについて説明しています。同姓同名のヴァイオリニストについては「マイケル・レビン」をご覧ください。

マイケル・ラビン（Michael Oser Rabin、1931年9月1日 - ）は、著名な計算機科学者であり、その分野で最も権威のあるチューリング賞を受賞した。

マイケル・ラビン
マイケル・ラビン(2004)
生誕	(1931-09-01) 1931年9月1日（93歳） ドイツ ヴロツワフ
国籍	イスラエル
研究分野	計算機科学
研究機関	ハーバード大学 ヘブライ大学 コロンビア大学
出身校	ヘブライ大学 M.S. プリンストン大学 Ph.D.
博士課程 指導教員	アロンゾ・チャーチ
博士課程 指導学生	サハロン・シェラハ
主な業績	ミラー-ラビン素数判定法 Rabin暗号 紛失通信プロトコル ラビン-カープ文字列検索アルゴリズム 非決定性有限オートマトン 乱択アルゴリズム
主な受賞歴	チューリング賞(1959)
プロジェクト:人物伝

経歴

1931年、ドイツのブレスラウ（現：ポーランド領ヴロツワフ）でラビの息子として生まれた。1935年、家族と共にイギリス委任統治領パレスチナに移住。少年のころ数学に強い関心を抱き、ハイファの最高の高校に進学。そこで当時高校教師として勤めていた優秀な数学者 Elisha Netanyahu に学ぶ^[1]。

高校卒業後、第一次中東戦争 (1948) の際に陸軍に徴兵された。エルサレムで教授を務めていた数学者アドルフ・フレンケルが軍の命令に介入し、ラビンは1949年に兵役から解放されてヘブライ大学で学べるようになった^[1]。1953年、ヘブライ大学で修士号を取得し、1956年にはプリンストン大学で博士号を取得している。

1950年代末、IBMが夏の間ニューヨーク州ウエストチェスター郡にある Lamb Estate に見込みのある若い数学者や科学者を招き、研究環境を与えた。その中にラビンも選ばれている。そこでデイナ・スコットと共に論文 "Finite Automata and Their Decision Problems"（有限状態機械とその決定性問題）を書いた^[2]。間もなく非決定性有限オートマトンを活用して、クリーネの「有限状態機械は正確に正規言語を受理する」という結論を再証明することができた^[1]。

後に計算複雑性理論と呼ばれることになる理論の原形を完成させるため、ラビンは翌年の夏も Lamb Estate に赴いた。ジョン・マッカーシーは彼にスパイと警備員とパスワードに関するパズルを提示。ラビンはそれを研究して論文 "Degree of Difficulty of Computing a Function and Hierarchy of Recursive Sets"（関数を計算する難しさの度合いと帰納的集合の階層）を書き上げた^[1][3]。

非決定性有限オートマトンは計算複雑性理論の重要な概念となった。特にP≠NP予想の説明の際に重要となる。

エルサレムに戻ったラビンは論理学を研究し、計算機科学と呼ばれることになる学問領域の基礎構築を行った。ヘブライ大学では準教授を務め、29歳で数学研究所の所長となり、33歳で正教授となった。当時についてラビンは「コンピューティング問題についての業績は全く評価されなかった。数学者らはこの新たな領域を全く認知していなかった」と述べている^[1]。

1960年、エドワード・F・ムーア（英語版）に招かれてベル研究所で働くことになり、状態遷移をコイントスで決める確率的オートマトンを考案。非常に多数の状態が必要な正規言語でも、確率的オートマトンなら劇的に状態数を減らせることを示した^[1]。

1969年、n 後者の二階述語論理が決定性であることを証明^[4]。その証明の重要な要素により、ボレル階層の第3レベルにあるパリティゲームの決定性（英語版）が暗に示される。

1975年、ヘブライ大学での在職期間を終了したラビンはアメリカのマサチューセッツ工科大学に行き、客員教授として勤めた。そこでゲーリー・ミラー（英語版）と出会う。ミラーは拡張リーマン予想に基づいた多項式時間の素数判定法を考案した。これをベースとしてラビンは拡張リーマン予想に依存しないミラー-ラビン素数判定法を発明した。これは、数が素数であるかどうかを非常に迅速に判定できる確率的アルゴリズムである（ただし間違う可能性が若干存在する）^[5][6]。公開鍵暗号にはRSA暗号のように大きな素数を秘密鍵とするものも多く、高速な素数判定法は鍵生成の実装に重要である。2003年、ミラーとラビンは他の関係者と共に素数判定法における業績を称えられ、Paris Kanellakis Award を受賞した。

1979年、ラビンはラビン暗号を発明した。それは、暗号文を解読する手間が公開鍵である合成数の素因数分解と同程度と証明された最初の公開鍵暗号である^[7]。

1981年、ラビンは紛失通信 (Oblivious Transfer) と呼ばれる手法を発明した^[8]。これは、送信側が2つのメッセージを送り、受信側がそのうち片方のみを受け取るが、送信側にはどちらを受け取ったか分からないというもので、マルチパーティプロトコルの部品としても使用される暗号プロトコルの要素技術の一つである。

1987年、ラビンはリチャード・カープとともに有名で効率的な文字列探索法、ラビン-カープ文字列探索アルゴリズムを開発した^[9]。

ラビンはその後コンピュータセキュリティの研究に集中している。彼はハーバード大学とヘブライ大学の計算機科学の教授である。2007年には、客員教授としてコロンビア大学で「暗号理論入門」を教えた。

米国科学アカデミーの外国会員であり、フランス科学アカデミーの会員であり、王立協会の外国会員である。

指導した学生としてサハロン・シェラハがおり、数理論理学の研究者として活躍している。

受賞歴

• 1959年にデイナ・スコットと共同で執筆した論文により、1976年にチューリング賞を授与された^[10]。受賞理由は次の通り。

「彼らの共作論文 "Finite Automata and Their Decision Problem"（有限状態機械とその決定性問題）に対して。その論文は非決定性マシンという非常に貴重な概念を導入した。この古典的論文はこの分野の後続の者たちに絶えずインスピレーションを与えてくれた」^[11]

• 1973年、ロスチャイルド賞を受賞。
• 1980年、ハーヴェイ賞を受賞。
• 1995年、イスラエル賞を計算機科学の研究で受賞した^[12]。
• 2010年、イスラエルのダン・デイヴィッド賞（未来部門）をレナード・クラインロックとゴードン・ムーアと共に受賞した^[13]。