希尔伯特(David Hilbert)在1928年提出了三个关于任意数学形式系统(formal system of mathematics)的基本问题：
(1) 这个系统的规则的集合是不是完备的(从而只需用此系统内的规则就可以证明或反证一个陈述)?
(2) 这个系统是不是一致的？ 也就是说没有任何一个陈述既可以被证明是真的也可以被证明是假的。
(3) 有没有这么一个步骤能够决定是否某个特别的陈述是可以被证明的，而不是某些陈述有可能处于不能被确定的中间状态。
希尔伯特认为前两个的答案是“是”。第三个他不能确定。
在接下来的三年里， 奥地利出生的逻辑学家库尔特·哥德尔(Kurt Godel)，揭开了前两个问题的答案。 答案出人意料： 不是， 不是。哥德尔给出这个答案的时候只有25岁，和妈妈住在维也纳。在他的"不完备定理"中，他指出存在既不能被证明也不能被反证的陈述，任意数学系统是不完备的。他也建立了其他的理论来有效的回答希尔伯特的第二个问题。
然而哥德尔的理论并不能解答第三个问题。第三个问题被希尔伯特称为"Entscheidungsproblem"(德语的意思是"确定性问题")。 这个问题在1937年被阿伦·图灵(Alan Turing)和阿隆佐·邱奇(Alonzo Church)解决了， 这一年，图灵也正好是 25岁。他们分别发表了论文指出希尔伯特的第三个问题是无解的。图灵的论文是"On Computable Numbers, with an Application to the Entscheidungsproblem"。但是比论文所做的证明更重要的是，图灵给出了后来影响计算机科学发展的"图灵机"的概念(论文中称为"逻辑计算器")。另一位贡献者邱奇提出了"λ演算(lamada calculus)"。 这一概念后来影响了LISP编程语言和函数式编程(functional programming)。
摘自
[1] "The Innovators" by Walter Isaacson
