In 1900, Professor David Hilbert gave a talk entitled "The Future of Mathematics" before the Second International Congress of Mathematicians in Paris (See Bulliten of the American Mathematical Society, vol. 8, 1902). In his talk Hilbert listed 23 problems that showed the breadth and depth of mathematics and represented challenges for mathematicians in the 20th century. Only three remain unsolved 6, 8, and 16. A Norwegian newspaper is reporting that 21-year old Elin Oxenhielm has solved the second part of problem 16 having to do with boundary cycles for polynomial differential equations.
Hilbert is of historic importance to Computer Scientists. Hilbert believed, as did many mathematicians of his day that (a) you could build a complete system of mathematics, capable of describing every problem, (b) that a valid sequence of steps in that system could never give an inconsistent answer (i.e. 2+2=5) and (c) that in that system, mechanical proof would be sufficient to discover every theorem (decidability). (Note that by "mechanical," Hilbert wasn't talking of machines or computers, but the rote application of rules.) Hilbert did not believe in unsolvable problems.
If you remember your computability theory correctly, Kurt Godel showed that (a) and (b) were not true---no system can be complete and consistent (known as Godel's Incompleteness Theorem). Godel's work did not show, however that there was no way to distinguish the provable from the unprovable. In other words (c) might still be true inside a incomplete, but consistent set of rules like the mathematics we use everyday. Every Computer Scientist knows of the halting problem wherein Alan Turing showed that (c) was not true either.
Interestingly, Turing's approach to solving the problem was to envision a machine, the Turing machine, and then show there were problems such a machine could not solve. Another mathematician, Alonzo Church, working on the same decidability question, took another approach and the result was Lambda Calculus, the basis for much of the formal work in programming languages and the inspiration for LISP. Turing very nearly did not get the credit he deserved for proving undecidability because Church published his results first. This wasn't the first such scrape for Turning. His PhD dissertation had been to show the Central Limit Theorem of statistics, not realizing that it was already solved. Only after his committee was convinced that he had worked in complete ignorance of the other work was he awarded his degree.
If you're interested in these things and like biographies, I can recommend several books.
- Hilbert-Courant by Constance Reid is a dual biography of Hilbert and Courant---two great mathematicians of the early 20th century. The biography is quite readable and understandable by anyone with an interest in mathematics.
- Alan Turing: The Enigma by Andrew Hodges is a book every computer scientist ought to read. The book does an excellent job of covering Turing's important and tragic life.
Its fascinating to me to know how broad the interests of men like Hilbert and Turing were. In Hilbert's day there was no such thing as applied mathematics. All mathematics was applied and it was not unusual for mathematicians and physicists to be interchangeable. I often wonder what the future holds for Computer Science. What are the links between the science and the $2 trillion per year IT industry. Does CS matter anymore? I believe the answer is yes, but I think computer scientists do a poor job of creating relevance. We've become less and less applied to the real problems of the day and seem to take a certain pride in that.
