CHAOS ATLAS HM-003

チューリング

「計算するとはどういうことか」を紙の上の小さな機械で言い表し、戦争では暗号を破り、戦後は機械が考えられるかを問い、最後には生き物の縞や斑点がどうできるかにまで手を伸ばしたのが、アラン・チューリングだった。

アラン・チューリング(1912〜1954年)は、1912年6月23日、ロンドンで生まれた。父はインドで働く英国の役人で、幼いころは両親と離れて英国の知人の家に預けられて育った。寄宿学校のシャーボーン校では、古典を重んじる学校の方針になじまず、教師からは理科と数学ばかりに打ちこむ変わり者とみられていた。そこで出会った1学年上の友人クリストファー・モーコムとは科学の話で深く結びついたが、モーコムは1930年に病気で急死する。この死は、心とは何か、心は体とどう結びつくのかという問いを、彼の中に長く残したとされる。1931年にケンブリッジ大学キングズ・カレッジに入り、1935年には22歳でカレッジのフェロー(研究員)に選ばれた。

その年に聞いた数学者ニューマンの講義で、彼はヒルベルトが掲げた問いの一つを知る。数学の主張が正しいかどうかを、決まった手順で機械的に判定する方法はあるか、という「決定問題」である。答えるには、まず「決まった手順」とは何かをはっきりさせなければならない。彼は、紙に記号を書いたり消したりしながら計算する人の動きを、ぎりぎりまで単純にした仮想の機械で言い表した。長いテープ、そのマス目を1つずつ読み書きする頭、いくつかの決まった状態だけでできた機械である。今はチューリングマシンと呼ばれるこの模型を使って、1936年の論文「計算可能な数について」で、判定の方法はありえないことを示した。投稿したのは24歳になる直前だった。同じ論文には、ほかのどんな機械の動きもまねできる「万能機械」の考えも書かれている。ほとんど同じころ、アメリカのチャーチが別のやり方で同じ結論に達しており、チューリングはその後プリンストン大学に渡って、チャーチのもとで1938年に博士号を取った。

第二次世界大戦が始まると、ロンドンの北西のブレッチリー・パークにある政府の暗号学校で、ドイツ軍の暗号機エニグマの解読に加わった。土台になったのは、ポーランドの暗号局の仕事である。数学者レイェフスキらは1930年代はじめにエニグマの仕組みを数学で読み解き、「ボンバ」と呼ぶ機械で鍵を探す方法まで作っていた。1939年7月、侵攻の直前に、その成果は英仏の担当者に引き渡された。チューリングは、文の一部の中身を推測できるときにそれを手がかり(クリブ)にして、矛盾しない機械の設定を電気仕掛けでしらみつぶしに調べる装置「ボンブ」を設計し、1940年3月に最初の1台が動き出した(のちに同僚ウェルチマンの改良が加わって、ずっと効率が上がる)。彼が受け持った「ハット8」は、とくに守りの固い海軍のエニグマを担当し、大西洋の補給路を襲うドイツの潜水艦Uボートの通信を読むことに貢献した。暗号の解読が戦争を何年縮めたかは、よく引かれる数字があるものの、どれも推定である。ブレッチリーで働き、のちに英国の情報活動の公式史をまとめた歴史家ハリー・ヒンズリーは、ここでの解読の仕事全体によって、戦争は少なくとも2年、おそらく4年ほど短くなったと述べている。ただし、述べた場によって挙げる年数は違い、もっと控えめに見る歴史家もいる。1943年はじめには訪米中に情報理論を生み出す前のシャノンと会い、機械と頭脳について語り合ったと伝えられる。

戦後は国立物理学研究所に移り、プログラムを記憶装置にしまう電子計算機 ACE を設計した。1945年のフォン・ノイマンによる EDVAC の報告書の草稿を踏まえつつ、回路の細部まで書きこんだ、より具体的な設計だった。ただ組み立ては遅れ、縮小版の Pilot ACE が最初のプログラムを動かしたのは1950年5月で、彼はその前の1948年にマンチェスター大学へ移っていた。そこでは実際に動く計算機のプログラムを書き、その使い方の手引きもまとめている。1950年の論文「計算機械と知能」では、「機械は考えられるか」という問いを、文字だけのやりとりで相手が人か機械かを見分けられるかという「模倣ゲーム」に置き換えた。これが今いうチューリングテストである。彼は、50年ほどあれば、5分間話したあとで普通の質問者が正しく見分けられる見込みを7割以下にする機械が作れるだろうと予想した。この考えには、外から見て会話ができても中身を理解しているとは限らないという中国語の部屋などの批判があり、今も議論が続いている。

1952年には、まったく別の分野の論文「形態形成の化学的基礎」を出した。受精卵はほとんど均一な細胞の集まりから始まるのに、どうして縞や斑点、指の並びのような形ができるのか。彼は、組織の中で2種類の物質が反応し合いながら広がっていくだけで、均一な状態がひとりでに崩れ、決まった間隔の模様が生まれることを計算で示した。これが形態形成の研究に今も残る「チューリング・パターン」の出発点である。晩年には、ヒマワリの種や松かさの並びにフィボナッチ数が現れる理由も、計算機を使って調べていた。

その1952年、彼の生活は大きく変わる。1月、自宅に入った空き巣のことで警察に届けた際、知り合った若い男性との関係を話し、当時の英国の法律で男性どうしの性的な関係を罰する「著しいわいせつ行為」の罪に問われた。3月31日に罪を認め、刑務所に入るか、1年間女性ホルモンの投与を受けることを条件に保護観察になるかを選ばされて、後者を選んだ。体にも変化が出たことが知られている。機密を扱う資格を失い、戦後も続けていた政府の暗号の仕事にも関われなくなった。1954年6月7日、彼はマンチェスター郊外ウィルムズローの自宅で亡くなり、翌日、家政婦に見つけられた。41歳だった。死因は青酸による中毒で、検死審問は自殺と評決した。ベッドのそばにかじりかけのりんごがあったが、そのりんごは毒物の検査をされていない。白雪姫の映画の毒りんごの場面を好んで口ずさんでいたとも伝えられ、りんごの話はそこから広く語られるようになった。一方で、家で化学の実験をしていた彼が誤って青酸を吸いこんだ事故だった可能性を指摘する研究者もいる。母親も事故だと信じていた。遺書は見つかっておらず、何があったのかを1つに決めることはできない。

彼の戦時中の仕事は長く機密とされ、広く知られるようになったのは1970年代以降である。2009年、ネット上の請願を受けて、ブラウン首相が政府として、彼が受けた扱いを謝罪した。2013年12月24日には女王の名で死後の恩赦が与えられ、2017年には、同じ法律で有罪とされたほかの多くの男性にも恩赦を広げる規定ができた。2021年6月23日、彼の誕生日に、肖像を刷ったイングランド銀行の50ポンド紙幣が発行されている。計算機科学でいちばん名の知れた賞が「チューリング賞」と呼ばれ、1966年から贈られていることも、この分野が彼をどう見ているかを物語っている。

決定問題に、機械で答える

決定問題(Entscheidungsproblem)は、1928年にヒルベルトとアッカーマンが論理学の教科書の中ではっきりした形で掲げた。論理の式が与えられたら、それが正しいかどうかを有限の手順で必ず判定できる方法があるか、という問いである。「ある」と示すなら方法を1つ見せればよいが、「ない」と示すには、ありうるすべての方法をまとめて相手にしなければならない。そのためにチューリングは、「機械的な手順」そのものを数学の対象として定義した。さらに、機械の動きを決める表は記号の列に書けるので、その列をテープに書いて読ませれば、1台の機械がどんな機械にもなれる。これが万能機械で、プログラムを入れ替えればどんな計算もこなす今の計算機の考えを、紙の上で先取りしていた(チューリング完全の考えもここから来ている)。そのうえで、任意の機械を渡されて、それが記号の0を書くことがあるかどうかを言い当てる機械は作れないことを示し、そこから決定問題の答えが「ない」ことを導いた。今は停止問題と呼ばれる形に整理されている論法で、中身はチューリングマシンで扱っている。

面白いのは、同じ答えが同じ年に別の道から出たことだ。プリンストンのチャーチは、関数をつくって当てはめる規則だけでできた体系(ラムダ計算、lambda calculus)で「計算できる」を定義し、1936年4月に出た論文で機械的には解けない問題があることを示し、続く短い論文で、決定問題を解く方法もないと導いていた。ケンブリッジでそれを知ったチューリングは、自分の論文に、2つの定義で計算できるものの範囲が一致することを示す付録を足した。「機械的に計算できるものは、まさにこの範囲だ」という主張は、今はチャーチ=チューリングのテーゼ(Church–Turing thesis)と呼ばれる。証明できる定理ではなく、定義を受け入れる理由の話であることに注意がいる。それでも、不完全性定理のゲーデルは、ラムダ計算で「計算できる」を定義しようというチャーチの提案には当初まったく納得しなかった一方で、1964年に書き足した追記では、チューリングの仕事が「機械的な手順」という考えを分析し、疑いなく適切な定義を与えたと述べている。このように、人が紙と鉛筆でする計算から出発した彼の定義は、説得力の点で抜けていた。

証拠の重さを足し算する バンとバンブリズム

海軍のエニグマを破るため、チューリングはベイズの考えで「証拠の重さ」を数える方法を作った。ある仮説 H(たとえば「この2通の通信は、同じ設定のもとでこれだけずらして重ねると揃う」)について、手がかり E が見つかったときの重さを、次の式で表す。

W = log₁₀ [ P(E | H) ÷ P(E | H でない) ]

P(E | H) は、仮説が正しいときにその手がかりが出る確率、P(E | H でない) は仮説が誤りのときに出る確率である。比が10倍のとき重さは1で、これを1バン(ban)、その10分の1を1デシバン(deciban)と呼んだ。対数をとってあるので、互いに無関係な手がかりの重さはただ足し算すればよい。助手を務めた統計学者グッドは、1デシバン前後が、人が直観で感じ取れる重さの変化の最小の単位くらいだと書き残している。

実際の作業では、2通の暗号文を細長い紙に打ち出して重ね、ずらし方を変えながら、同じ文字が同じ位置に来る回数を数えた。でたらめな文字列どうしなら一致は26分の1ほどだが、同じ設定で暗号化されたドイツ語の文どうしなら、元の文の文字の偏りのせいで一致がそれより多くなる。一致1つごとにわずかな重さを足していき、合計が大きくなった組み合わせから、暗号機の歯車の並べ方の候補を絞りこむ。ボンブを動かす前に候補を減らせれば、限られた台数の機械を有効に使える。紙はブレッチリーに近い町バンベリーで印刷されたので、この手順はバンブリズム(Banburismus)と呼ばれ、単位のバンもそこから名づけられた。手がかりの重さを情報の量として足し合わせる考えは、のちの情報理論とも通じている。

縞と斑点の化学

1952年の論文の中心にあるのは、反応拡散方程式(reaction–diffusion equation)と呼ばれる形の式である。

∂u/∂t = f(u, v) + Dᵤ∇²u
∂v/∂t = g(u, v) + Dᵥ∇²v

u と v は2種類の物質の濃さ、∂/∂t は時間とともにどれだけ変わるか、f と g は2つの物質が互いを増やしたり減らしたりする反応、∇² は周りより濃い所から薄い所へならされていく拡散の働き、Dᵤ と Dᵥ はそれぞれの広がりやすさである。チューリング自身は物質を「モルフォゲン」(morphogen、形をつくる物質)と呼んだ。のちに整理された言い方では、u が自分自身と v を増やす「活性化因子」、v が u を抑える「抑制因子」で、抑制因子のほうがずっと速く広がるとき、模様ができる。どこかで u が少し濃くなると、その場所ではさらに濃くなるが、同時に作られた v が速く周りに広がって、近くで別の山ができるのを抑える。拡散はふつう物をならす働きなのに、広がる速さが違うと逆に模様を生む。これが彼の見抜いた点で、外から設計図を与えなくても形がひとりでに現れる自己組織化の、代表的な例になった。

論文が出てからしばらく、この考えは生物学ではあまり顧みられなかった。流れが変わったのは数十年後である。1995年、近藤滋らは、サザナミヤッコなどキンチャクダイの仲間(ポマカントゥス属)の熱帯魚の縞が、体が大きくなるにつれて間に新しい縞を加えて数を増やしたり、枝分かれの位置を動かしたりする様子が、反応拡散の模型の計算とよく合うことを示した。2006年にはシックらが、マウスの毛の生える間隔が、WNT というたんぱく質と、それを抑える DKK の組み合わせで決まることを実験で確かめ、2012年にはエコノモウらが、マウスの口の中の上あごに並ぶひだが同じ仕組みでできることを報告している。どの模様がどこまで反応拡散で説明できるかは、生き物ごとに今も検証が続いており、実際には2種類より多くの物質や、細胞どうしの直接の働きかけが関わる例も見つかっている。それでも、2つの物質と広がる速さの違いだけで形が生まれるという1952年の発想は、形態形成を考えるときの基本の道具の一つになっている。

REFERENCES

  1. A. M. Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society s2-42, 230–265 (1936–37)↗
  2. A. Church, "An Unsolvable Problem of Elementary Number Theory", American Journal of Mathematics 58, 345–363 (1936)↗
  3. A. M. Turing, "Computing Machinery and Intelligence", Mind 59, 433–460 (1950)↗
  4. A. M. Turing, "The Chemical Basis of Morphogenesis", Philosophical Transactions of the Royal Society of London B 237, 37–72 (1952)↗
  5. I. J. Good, "Studies in the History of Probability and Statistics. XXXVII: A. M. Turing's Statistical Work in World War II", Biometrika 66, 393–396 (1979)↗
  6. S. Kondo, R. Asai, "A reaction–diffusion wave on the skin of the marine angelfish Pomacanthus", Nature 376, 765–768 (1995)↗
  7. S. Sick, S. Reinker, J. Timmer, T. Schlake, "WNT and DKK Determine Hair Follicle Spacing Through a Reaction-Diffusion Mechanism", Science 314, 1447–1450 (2006)↗
  8. A. D. Economou et al., "Periodic stripe formation by a Turing mechanism operating at growth zones in the mammalian palate", Nature Genetics 44, 348–351 (2012)↗
  9. J. R. Searle, "Minds, brains, and programs", Behavioral and Brain Sciences 3, 417–424 (1980)↗
  10. A. Hodges, Alan Turing: The Enigma, Burnett Books (1983) /邦訳 A. ホッジス『エニグマ アラン・チューリング伝』上・下、土屋俊・土屋希和子訳(下巻は村上祐子との共訳)、勁草書房(2015) 下 ISBN 978-4-326-75054-2、上↗
  11. B. J. Copeland (ed.), The Essential Turing, Oxford University Press (2004)↗

Amazonのアソシエイトとして、CHAOS ATLAS は適格販売により収入を得ています。

RELATED

ABOUTPRIVACY

Alan TuringHM-003 / 定説