Decidability Problem

The decidability problem (Entscheidungsproblem) was one of a set of challenges – the Hilbert program --  offered to mathematicians by David Hilbert at the International Mathematical Congress held in Paris in 1900 (Prager, 2001).  The decidability problem is this: does there exist a “definite method” that, when given any possible statement in mathematics, can decide whether that statement is true or false?  Hilbert believed that the answer to this question would be “yes”.  However, one of Alan Turing’s great achievements was to prove that the answer to the decidability problem was “no” (Hodges, 1983; Turing, 1936).

In order to prove that the answer to the decidability problem was “no”, Turing had to develop a definite method that was simple enough to be accepted by mathematicians who read his proof, but at the same time was powerful enough to be considered as a plausible contribution to the Hilbert program.  Another of Turing’s great achievements was the development of the Turing machine, which in his 1936 paper served the role of definite method.  The Turing machine became the foundation of modern digital computers, and the foundation of classical cognitive science.

References:

1. Hodges, A. (1983). Alan Turing: The Enigma Of Intelligence. London: Unwin Paperbacks.
2. Prager, J. (2001). On Turing. Belmont, CA: Wadsworth/Thomson Learning.
3. Turing, A. M. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series 2h, 42, 230-265.