アラン・チューリング

OBE, FRS 1912年6月23日 - 1954年6月7日）は

1928年、ドイツの数学者ダフィット・ヒルベルトは、「決定問題」への注目を呼びかけた。

（「計算可能数、ならびにそのヒルベルトの決定問題への応用」、1936年5月28日提出、11月12日配布）で、

この問題の解決に重要な役割を果たした。

この論文の重要な点を、現代の数学および数学基礎論およびコンピュータ科学の視点からまとめると次のようになる。

19世紀以前の数学では数理論理の視点からすると自然言語で記述されるなど曖昧な点があったアルゴリズムを

形式的に表現する手法（のひとつ）を確立し、

「何らかのチューリングマシンで計算可能な関数を計算可能関数とする」という計算可能性理論における重要なテーゼ

（チャーチの業績とは独立であり、チューリングのほうがよりわかりやすく直感的であった。人によってはチューリング＝チャーチのテーゼ、の順とすることもある）。

(2)どんなチューリングマシンの動作をも、現代の言葉で言えば「エミュレート」できる、「万能チューリングマシン」が可能であることを証明し、その構成法を示した。

（注意: この(1)と(2)が表現していることを曖昧に理解しないように注意すること。

「テーゼ」は証明ではない（証明できるような性質のものではない）。

しばしば、万能チューリングマシンによりあらゆる計算が可能であることを証明した、というような誤解が見受けられる。）

(3)「万能チューリングマシン」の概念を利用して、停止性問題を否定的に証明した

（これはゲーデルの不完全性定理と同等の結果とも言えるものである。詳細は停止性問題の記事を参照）。