大学時代と計算可能性についての研究
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/05 04:54 UTC 版)
「アラン・チューリング」の記事における「大学時代と計算可能性についての研究」の解説
ケンブリッジ大学キングス・カレッジへ進学した。1931年から1934年まで学生として学び、数学で優秀な成績を修めて卒業した。1935年に、中心極限定理を証明した論文が認められ、キングス・カレッジのフェロー（特別研究員）に選ばれた。ただし、中心極限定理は1922年にJ・W・リンデベルグ（英語版）が証明済みだったが、チューリングはその業績を知らなかった。 1928年、ドイツの数学者ダフィット・ヒルベルトは、「決定問題」への注目を呼びかけた。チューリングは、重要な論文 "On Computable Numbers, with an Application to the Entscheidungsproblem"（「計算可能数、ならびにそのヒルベルトの決定問題への応用」、1936年5月28日提出、11月12日配布）で、この問題の解決に重要な役割を果たした。 この論文の重要な点を、現代の数学および数学基礎論およびコンピュータ科学の視点からまとめると次のようになる。(1)「チューリングマシン」という計算モデルを提示し、19世紀以前の数学では数理論理の視点からすると自然言語で記述されるなど曖昧な点があったアルゴリズムを形式的に表現する手法（のひとつ）を確立し、「何らかのチューリングマシンで計算可能な関数を計算可能関数とする」という計算可能性理論における重要なテーゼであるチャーチ＝チューリングのテーゼを示した（チャーチの業績とは独立であり、チューリングのほうがよりわかりやすく直感的であった。人によってはチューリング＝チャーチのテーゼ、の順とすることもある）。(2)どんなチューリングマシンの動作をも、現代の言葉で言えば「エミュレート」できる、「万能チューリングマシン」が可能であることを証明し、その構成法を示した。（注意: この(1)と(2)が表現していることを曖昧に理解しないように注意すること。「テーゼ」は証明ではない（証明できるような性質のものではない）。しばしば、万能チューリングマシンによりあらゆる計算が可能であることを証明した、というような誤解が見受けられる。）(3)「万能チューリングマシン」の概念を利用して、停止性問題を否定的に証明した（これはゲーデルの不完全性定理と同等の結果とも言えるものである。詳細は停止性問題の記事を参照）。 1936年9月から1938年7月にかけて、プリンストン高等研究所においてアロンゾ・チャーチ（前述の「チャーチ＝チューリングのテーゼ」のチャーチである）に師事した。1938年、プリンストンで博士号を得た。博士論文では、数の広がり（正の整数→負数→無理数→虚数）とその公理体系の進化に関して、それらすべてを包含する「順序数」という概念の体系を整理しようとした。その中で、チューリング還元の概念を提案している。純粋数学とは別に暗号理論もここで学び、電気機械式乗算器も試作している。また、この時期、ジョン・フォン・ノイマンも同じくプリンストンにおり、二人は親交があったと言われている。ノイマンは、チューリングにアメリカに残ることを勧めたという。 1939年にケンブリッジに戻ると、ウィトゲンシュタインとの講義に参加した。そこでは、ウィトゲンシュタインが「数学は絶対的真実を発見するのではなく、発明している」という立場を取ったのに対して、チューリングは形式主義を擁護する立場を取った。
※この「大学時代と計算可能性についての研究」の解説は、「アラン・チューリング」の解説の一部です。
「大学時代と計算可能性についての研究」を含む「アラン・チューリング」の記事については、「アラン・チューリング」の概要を参照ください。
- 大学時代と計算可能性についての研究のページへのリンク
