2.1 Limits in theory
The first general-purpose digital computers were built from around 1940 onwards. With the actual construction of such machines, Leibniz’s dream seemed to be very close to becoming reality. However, this first generation of computers was built with government funding for military and intelligence purposes (during the Second World War), rather than for Leibniz’s original aim of settling disputes peacefully.
Even before these computers were built, mathematicians such as Kurt Gödel (1906–1978) and Alan Turing (1912–1954) discovered that there are definite limits to what they can do. This came about as follows.
The idea of a purely ‘mechanical’ way to prove or disprove a claim appealed greatly to mathematicians of the early 20th century interested in the foundations of mathematics. By then, mathematics itself had reached a stage where it was no longer the bastion of certain knowledge that it used to be. The mathematician and philosopher Bertrand Russell (1872–1970) had discovered a contradiction at the heart of mathematical language itself. There was a distinct fear that further, as yet, undiscovered contradictions might surface. Any resolution using a method that was guaranteed to yield certain knowledge was extremely welcome.
The question arose whether there is a mechanical procedure for determining whether a set of mathematical statements is true. What is a mechanical procedure? A mechanical procedure is a collection of rules that, once grasped, can be applied step-by-step without requiring any ingenuity. Such rules allow us to, for instance, perform a column addition. Once you have mastered column addition, you can carry it out without any creativity or flashes of insight. The rules can be applied in a ‘mechanical’ way (see Figure 8).
Gödel’s and Turing’s work demonstrated conclusively that there is no collection of rules for calculating whether any set of mathematical statements is true. Determining whether a set of mathematical statements is true can’t be automated.