From Turing To Dijkstra In the July 2011 issue of the
Communications of the ACM you will find on page 5 a section
entitled "Solving the Unsolvable", written by the editor in
chief, Moshe Y. Vardi. In his words: In 1936–1937, Alonzo
Church, an American logician, and Alan Turing, a British
logician, proved independently that the Decision Problem for
first-order logic is unsolvable; there is no algorithm that
checks the validity of logical formulas. The Church-Turing
Theorem can be viewed as the birth of theoretical computer
science. To prove the theorem, Church and Turing introduced
computational models, recursive functions, and Turing machines,
respectively, and proved that the Halting Problem—checking
whether a given recursive function or Turing machine yields an
output on a given input—is unsolvable. The previous passage is
inaccurate in several respects. First, it is perhaps more
appropriate to say that Alan Turing was a mathematician, not a
logician. Second, even if Turing proved the Decision Problem
indep