映画「イミテーション・ゲーム（The Imitation Game）」を、いつものように太平洋上の飛行機の中、質の悪いイヤホーンで聞き取り難い音声に苦しみながら観ることができた。第二次世界大戦中のドイツ軍のエニグマ暗号解読に成功したアラン・チューリングの才能と人間性、そして同性愛者としての悲劇が描かれていて、かなり引き込まれた。1952年、当時イギリスで違法だった同性愛行為の罪で逮捕されたチューリングは、監獄に入るか薬物投与を受けるかの選択を迫られ、薬物投与を選んだ。1954年に自宅で死んでいるのを発見されたが、自殺だったのか事故死だったのか、あるいは殺人だったのか、はっきりしていない。2009年になってようやくイギリス政府は、チューリングに施された非人道的な薬物投与について謝罪、その後2013年にはエリザベス女王の名で恩赦を受けチューリングの名誉は回復された。2021年までに発行される予定のイギリスの新50ポンド紙幣には、チューリングの肖像が載ることになっているとか。

暗号解読で中心的役割を果たす以前の1936年、23歳のチューリングは「On Computable Numbers, with an Application to the Entscheidungsproblem（計算可能数、ならびにそのヒルベルトの決定問題への応用）」という、題名からはどんな内容なのか全くわからない、数学の基礎論に関する論文（以下＜論文＞と記す）を発表している。＜論文＞でチューリングが使った思考実験的な、つまり実際に存在するのではなく頭の中で考えた仮想機械が、その後のコンピューターの発明・発展に重要な貢献をした。この仮想機械はチューリング・マシーンと呼ばれている。

この＜論文＞の二つの点に注目したい。1．チューリングは何のためにチューリング・マシーンを発想したのか、2．チューリング・マシーンは、その後のコンピューター技術の発展にどういう影響を与えたのか。

第1点を理解するために、「ヒルベルトの決定問題」と訳されているEntscheidungsproblemの概略をわからないといけない。ドイツの数学者、ダフィット・ヒルベルト（David Hilbert）が1900年に23の未解決問題の1つとして提起した時点では、Entscheidungs der Lösbarkeitと表現されていて、英訳はdetermination of solvability、つまり、解くことができるかどうかを決定すること、という意味だろう。1920年代にヒルベルトは数学全体を公理体系化することを目指した。その文脈に置くと、Entscheidungsproblem（決定問題）はおおよそ次のようなことだと思われる。

ある公理体系内の定理・命題・問題を解くために、機械的に実行される有限個の一連の操作指示が存在するかどうかを決定できるか、という問題提起だ。「機械的に実行される有限個の一連の操作指示」というのは、現代の言葉で言うとアルゴリズムと同じことだ。注意すべきは、「解が存在するか」ではなく、「解が存在するかしないかを決定できるか」、つまり、決定可能性を問題にしている点だ。

チューリングの＜論文＞はこの「ヒルベルトの決定問題」に対する解答で、そういったアルゴリズムは必ずしも存在しないことを証明した。その為に使ったのが上で触れたチューリング・マシーンという仮想機械で、これは結局、人間の脳の論理・計算作用を形式化・モデル化したものと考えられる。

ここまで書いて、少し息が切れてきた。続きは次回に廻して、1936年＜論文＞にまつわる次のような逸話でお茶を濁して週末はゆっくり休むことにしよう。

ケンブリッジのキングス・カレッジの研究員（fellow）だったチューリングが＜論文＞の草稿を教授のマックス・ニューマン（Max Newman）に渡した時（1936年4月頃）、ニューマンの手元には「ヒルベルトの決定問題」に関するもう一つ別の論文が届いていた。アメリカの数学者アロンゾ・チャーチ（Alonzo Church）の論文の抜き刷りで、チューリングと同じ結論に達していた。チャーチの論文はすでに掲載されることが決まっていたので、チューリングの＜論文＞は時すでに遅く、本来であれば陽の目を見ない可能性が高い。ニューマンはしかしチューリングの証明方法のユニークさに注目し、London Mathematical Societyに提出することを勧めた。＜論文＞は1936年5月28日に提出され、11月12日に会議で発表、1937年に雑誌に掲載されている。その一方で、ニューマンは1936年5月31日頃アロンゾ・チャーチに手紙を書き、チューリングの＜論文＞がチャーチと同じ結論に達しているが、非常に異なった方法でそれを証明している、チューリングがそちら（プリンストン）に行ってあなたのもとで研究できないだろうか、と頼んでいる。1936年9月から1938年7月まで、チューリングはプリンストン大学のチャーチのもとで研究した。チューリング・マシンという造語を最初に使ったのは、チャーチだと言われている。（この段落は、Charles Petzold、The Annotated Turing、2008、pp. 60-63によった。）