# Alan Turing ## 概要 Alan Turing は、計算機科学の歴史における最重要人物として *Mathematics for Computer Science* 第8章(Number Theory)で紹介される。24歳のとき論文 "On Computable Numbers, with an Application to the Entscheidungsproblem"(1936年)を著し、計算機を数学的にモデル化する方法(チューリングマシン)を示した。この論文で David Hilbert が1900年に提起した Entscheidungsproblem(決定問題)を解決するとともに、いかなる計算機にも解けない問題が存在することを証明し、Church-Turing thesis の元にもなった。この論文が発表されたのは実際の電子計算機が登場する10年も前だった。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 8 Number Theory]] ch.8 §8.5) 1937年、Turing は第二次世界大戦を予見し、数論に基づく秘匿通信方式(本書が "Turing's Code" と呼ぶもの)を着想したとされる。詳細は Turing が正式に発表しなかったため不確かだが、本書では2通りの解釈が示される。Version 1.0(通常の整数上でメッセージに素数の鍵を掛ける方式)は、同じ鍵で2通のメッセージを送ると2つの暗号文の gcd が鍵そのものになるという致命的な欠陥を持つ。Version 2.0(素数を法とする合同算術上で鍵を掛ける方式)は改善されているが、既知平文攻撃(平文と暗号文の対が1組漏れると Pulverizer で鍵を復元できる)に弱い。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 8 Number Theory]] ch.8 §8.5.1〜§8.5.2, §8.9.3〜§8.9.4) 1939年、Turing は Bletchley Park の英国暗号解読チームに参加し、ドイツ海軍の Enigma 暗号の大量・迅速な解読手法の開発を主導した。この成果は北大西洋の輸送船団を U-boat から守る上で決定的に重要だったが、その功績が公式に明かされたのは1996年のことだった。戦後、Turing は自宅の窃盗事件の捜査を機に、当時イギリスで犯罪とされていた同性愛の罪で有罪となり、エストロゲン注射によるホルモン「治療」を強制された。3年後、Turing はシアン化カリウムによる中毒で死去した。母親は事故だと説明したが、他の伝記作家は Turing が以前から毒りんごによる自殺について話していたことを指摘している。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 8 Number Theory]] ch.8 §8.8, §8.9.5) ## 関連 - 書籍: [[Mathematics for Computer Science]] — 第8章(Number Theory)で生涯と暗号への貢献を紹介 - 概念: [[公開鍵暗号方式]] — Turing の着想(数論に基づく秘匿通信)は RSA の先駆けとして位置づけられる - 概念: [[合同算術]] — Turing's Code Version 2.0 が用いる素数を法とする合同算術 ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 8, §8.5, §8.8〜§8.9.