Who was David Hilbert?
David Hilbert was a German mathematician, living in the late 19th and early 20th centuries, who made valuable contributions to numerous areas of Mathematics and Physics.
Here are just two of the more interesting examples of his contributions to science:
David Hilbert is probably best known for his invention of the Hilbert Space, which not only is an important concept in the field of mathematics known as Functional Analysis, but is also a useful tool in Quantum Physics.
In 1915, Albert Einstein visited David Hilbert at the University of Gottingen and they discussed the General Theory of Relativity that Einstein was working on. Einstein was having difficulty in deriving the field equations which would give the General Theory of Relativity its final form, and was beginning to believe that it may not even be possible. Hilbert told him that he felt that it probably could be done.
Encouraged by Hilbert, Einstein went back and continued working on deriving the field equations. He succeeded! Meanwhile, Hilbert also tried to derive the field equations, and he succeeded as well! Both published their results.
This started a big controversy in the scientific community that continues till this day. There are those who say that Hilbert should be given credit for the General Theory of Relativity. Others claim that it should go to Einstein.
Hilbert himself said that the credit for the General Theory of Relativity belongs to Einstein.
Although David Hilbert made many other contributions to mathematics, they are too numerious to mention on this web page. For the rest of this web page, we'll only mention those facts that are pertinent to the development of the Turing Machine.
Before we refer to the famous speech that David Hilbert gave in 1900 (which is what really started the events leading up to the Turing Machine), it's worth mentioning that David Hilbert was a firm believer in the completeness of mathematics. He believed that any mathematical statement can either be proved to be true as a theorem, or proved to be false by counterexample. He also believed that any problem in mathematics can be solved, and in fact can be solved by some step-by-step method that can be applied to any problem. He believed that it was only a matter of time before we reach this level of perfection.
By the year 1900, Hilbert had already earned the reputation for being the greatest mathematician alive. He was invited to give a major speech at the Second International Congress of Mathematicians which was to be held in Paris in August of that year. For his speech, he decided to introduce his list of 24 problems that he believed should be the focus of mathematical research in the 20th century.
This speech turned out to be a very important event in the history of mathematics, since many mathematicians all over the world took up the challenge to try one or more of these problems. Some have been resolved, but others are still being worked on.
Of these 24 problems, there are two that had a direct impact on developments leading to the Turing Machine.
Problem #2: Prove that arithmetic is consistent.
Proving that arithmetic is consistent means proving that there can be no contradictions in arithmetic (or in all of mathematics, for that matter).
Problem #10: Develop some kind of method (i.e., an algorithm) that can be applied to any Diophantine Equation (or set of Diophantine Equations), and it will tell you if there are any solutions, and if there are solutions, it will find them.
When David Hilbert presented this problem in German, he used the words "Entscheidung der Lösbarkeit einer diophantischen Gleichung." In English, this means "Decision of solvability of a Diophantine Equation."
Notice that Hilbert used the word "Entscheidung" which means "Decision." He has not yet used the famous word "Entscheidungsproblem" because that word hasn't been invented yet. That'll come later--around 1928.
In the years 1910 through 1913, Alfred North Whitehead and Bertrand Russell published the three-volume book Principia Mathematica.
The purpose of this book was to place mathematics on a very firm logical foundation.
In the year 1928 David Hilbert gave a major address at the International Congress of Mathematicians in Bologna, Italy, at which he posed the following three questions:
1. Is mathematics complete?
I.e., can every true statement in mathematics be proved as a theorem?
2. Is mathematics consistent?
I.e., can we prove that there can never be any contradictions in mathematics?
3. Is mathematics decidable?
I.e., can a step-by-step method be devised (i.e., some kind of algorithm) that, when applied to any true statement in mathematics, will provide a proof of that statement.
This third question of Hilbert became famously known by a new word: Entscheidungsproblem.
Hilbert was confident that the answers to all three questions was yes (especially the first two questions), but it sure would be nice to have proofs of them as theorems.
In 1931, Kurt Gödel published a paper which became famously known as Gödel's Incompletenss Theorem.
Strictly speaking, what Gödel actually did was prove that mathematics is either inconsistent or incomplete, but it cannot be both consistent and complete. However, for mathematics to be inconsistent would just be unthinkable! That would imply that mathematics is useless!
For that reason, Gödel's Theorem is called an Incompleteness Theorem.
There is a story that when Hilbert first heard of Gödel's Incompletenss Theorem, he was angry. However, since it was a theorem with an impeccable proof, he had no choice but to reluctantly accept it.
Even though we know that mathematics is incomplete, the question of Entscheidungsproblem can still be asked. This time, it may be paraphrased as "Can a step-by-step method be devised, so that when applied to any true statement in mathematics, it will determine whether it is provable, and if so, will provide a proof of that statement?"
In 1936, Alonzo Church published a paper entitled A Note on the Entscheidungsproblem.
This settled the question of the Entscheidungsproblem: There is no step-by-step procedure that can be applied to any true statement in mathematics that will decide if it is provable. Church did this by using a new formal system in mathematical logic which he invented and called the λ-calculus.
In that same year 1936, Alan Turing published a paper entitled On Computable Numbers, with an application to the Entscheidungsproblem.
In his paper, Turing described a machine (which everyone later called the Turing Machine) and used it to come up with the same conclusion about the Entscheidungsproblem as Church did.
Actually, Turing's main purpose in inventing his Turing Machine was to show that not all numbers were computable. (Today, we might say that this implies that "Computers can't do everything.") Turing's paper consists of 11 sections, and it was finally in the last section, Section 11, that Turing showed how his Turing Machine could be used to resolve the Entscheidungsproblem--almost as if it were just an afterthought.
In 1915, Albert Einstein visited David Hilbert at the University of Gottingen and they discussed the General Theory of Relativity that Einstein was working on. Einstein was having difficulty in deriving the field equations which would give the General Theory of Relativity its final form, and was beginning to believe that it may not even be possible. Hilbert told him that he felt that it probably could be done.
Encouraged by Hilbert, Einstein went back and continued working on deriving the field equations. He succeeded! Meanwhile, Hilbert also tried to derive the field equations, and he succeeded as well! Both published their results.
This started a big controversy in the scientific community that continues till this day. There are those who say that Hilbert should be given credit for the General Theory of Relativity. Others claim that it should go to Einstein.
Hilbert himself said that the credit for the General Theory of Relativity belongs to Einstein.
Notice that Hilbert used the word "Entscheidung" which means "Decision." He has not yet used the famous word "Entscheidungsproblem" because that word hasn't been invented yet. That'll come later--around 1928.
This third question of Hilbert became famously known by a new word: Entscheidungsproblem.
For that reason, Gödel's Theorem is called an Incompleteness Theorem.
There is a story that when Hilbert first heard of Gödel's Incompletenss Theorem, he was angry. However, since it was a theorem with an impeccable proof, he had no choice but to reluctantly accept it.
Actually, Turing's main purpose in inventing his Turing Machine was to show that not all numbers were computable. (Today, we might say that this implies that "Computers can't do everything.") Turing's paper consists of 11 sections, and it was finally in the last section, Section 11, that Turing showed how his Turing Machine could be used to resolve the Entscheidungsproblem--almost as if it were just an afterthought.
Version 1.0 -- April 23, 2017