The Events That Led To The Turing Machine

---

The question that intrigued many mathematicians for hundreds of years is this: Is mathematics complete? By that is meant: Given any mathematical statement, can it be shown to be true or false?

Mathematics, as a logical system, is rather complicated. However, there are simpler, more limited logical systems, that can in fact be shown to be complete.

Perhaps the simplest one is the Propositional Calculus which a student of mathematics or philosophy might first encounter in a class on Symbolic Logic. It is here that you encounter statements such as "If A is true, and if A implies B, then B is true." In Propositional Calculus, it would be written symbolically as

Statements such as the one above can easily be verified to be true by using Truth Tables. Of course, statements in Propositional Calculus can also be very long with many letters and operators. The truth tables to verify these statements necessarily become quite large as well.

There is another method that can be used to prove statements in Propositional Calculus, and it is the method of Natural Deduction. Natural Deduction for Propositional Calculus was invented by the Polish logician Jan Łukasiewicz. It is practically identical to the method learned by high school students in a geometry class where they start with some Postulates or Axioms and after several steps and reasons arrive at a Theorem. (By the way, I was very surprised when I read on page 5 in the book Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman (Addison-Wesley, 2001, 2nd Edition) that since the 1990's, they don't teach "deductive proofs" in high schools in the USA anymore.)

Jan Łukasiewicz also proved a very important theorem that says the following: Propositional Calculus is consistent and complete. Consistent means that there are no contradictions. Complete means that every true statement can be proved.

---

---

In 1889, the Italian mathematician Giuseppe Peano published a set of axioms that became known as the Peano Axioms. When these are added to what we already have in Propositional Calculus, then we have a logical system that includes what we would recognize as arithmetic. It's a logical system that includes all the whole numbers, addition, multiplication, inequalities, etc. More specifically, we now have a logical foundation for proving theorems in the field of mathematics known as Number Theory.

This was truly a great breakthrough in mathematics! Mathematicians now had a way of approaching theorems in Number Theory that had the look and feel of doing proofs in Symbolic Logic. Most importantly, what this meant was that this approach gave mathematicians a feeling that, if not for all of mathematics, at least there was hope of proving that Number Theory is consistent and complete. It probably wouldn't be too long before some lucky mathematician would prove that there are no contradictions in Number Theory, and that every true statement in Number Theory can be proved, and thereby become very famous!

---

There is a subfield of Number Theory called Diophantine Equations named after the ancient Greek mathematician Diophantus. Diophantine problems involve solving a set of equations for more than one variable, but the solutions must be whole numbers. Here is an example of a Diophantine problem:

This problem can be written as the following two simultaneous equations in three variables. Just remember that the solution must be whole numbers.

Compared with other Diophantine problems, this is a rather easy one. It has only one solution. (Have you figured it out yet?)

Although much more could be said about Diophantine Equations at this point, I would rather continue with the other events that led to the Turing Machine, before we lose that train of thought. If you would like to find out more about Diophantine Equations, (including what the solution is to how many birds the poultry farmer sold), please click on the question "What are Diophantine Equations?" toward the bottom of this page.

---

In the year 1900, perhaps the most respected mathematician in the world was David Hilbert. The Second International Congress of Mathematicians was to be held in Paris in August of that year, and Hilbert was invited to give a major address. He decided that he would speak about what he considered the most important unsolved problems in mathematics that were just begging to be solved in the 20th century. He made a list of 24 problems, but time constraints of the speech allowed him to discuss only the first ten.

Needless to say, Hilbert's famous speech played a major role in influencing mathematical research in the 20th century.

Hilbert's second problem asks that arithmetic be proved to be consistent. What he probably had in mind was a proof within the Logical System that includes the Peano Axioms (described above on this webpage) that Number Theory is consistent (meaning no contradictions) and complete (meaning that every true statement can be proved). I'm sure he felt strongly (as did everyone else) that all of mathematics is both consistent and complete; but he only mentioned the word "consistent" in the statement of this problem, because he probably felt that "consistent" was more important than "complete".

Hilbert's tenth problem asks that someone devise a method which, when applied to any set of Diophantine Equations, could decide whether a solution exists. In today's language, we might rephrase the assignment as "Please design an algorithm that can be used to determine whether any given set of Diophantine Equations has a solution" or perhaps, what is equivalent "Please write a computer program which can read in any set of Diophantine Equations and decide whether a solution exists or not."

---

Many mathematicians felt that, in order to address the second problem that David Hilbert presented in Paris in 1900, mathematics must first be placed on a very firm logical foundation. What this means is that all of the theorems in mathematics must be derived using the Natural Deduction used in Symbolic Logic, starting with only a few self-evident axioms.

Two mathematicians, Alfred North Whitehead and Bertrand Russell decided to take this historic task upon themselves. They planned to jointly author a book in which they would start with the basic axioms of logic along with the Peano Axioms and derive the most basic theorems of mathematics. They also decided that the title of this book would be Principia Mathematica.

This turned out to be a truly monumental task. Volume 1 was published in 1910, followed by Volume 2 in 1912 and Volume 3 in 1913. Every assertion in these three volumes was derived in extremely painful detail, and it wasn't until Volume 2 that you could see the proof of "1 + 1 = 2".

I myself remember that back in 1965, when I was a freshman at Wayne State Univesity, the main branch of the Detroit Public Library was within walking distance from the university campus. It had a copy of Principia Mathematica. I remember being impressed with how much space those three volumes took up on the bookshelf.

Principia Mathematica did not contain a proof that mathematics is consistent and complete (as perhaps Whitehead and Russell hoped to do), but it was regarded as a great and important step in the right direction. It is considered to be one of the greatest nonfictional books written in the 20th century.

---

In 1928, David Hilbert gave a major address at the International Congress of Mathematicians in Bologna at which time he posed three very important questions which may be summarized as follows:

Hilbert's tenth problem from 1900 and his third question from 1928 became widely known by the name Entscheidungsproblem. Translated from German to English, "Entscheidungsproblem" means "Decision Problem."

Most, if not all, mathematicians, including David Hilbert, felt that the answer to all three questions was yes, and it was just a matter of time before someone would provide a proof.

---

Then, in 1931, something truly amazing happened!

It was in that year that a young Austrian mathematician Kurt Gödel wrote a very important paper with the title, which when translated from German to English, would read "On Formally Undecideable Propositions of Principia Mathematica and Related Systems I". As time went on, mathematicians would simply refer to this paper as Gödel's Incompleteness Theorem.

What Gödel did in his Gödel's Incompletenss Theorem was to take some of the methods and results presented in the Principia Mathematica of Whitehead and Russell, and using them, prove that mathematics is incomplete!

This means that there are statements that can be made in mathematics that are true, but can never be proved as theorems!

Furthermore, since mathematics is incomplete, it cannot be proved to be consistent as well. (However, mathematicians believe that the portion of mathematics that can be proved as theorems is consistent.)

Needless to say, this was a great surprise to David Hilbert and most, if not all, of the world's mathematicians.

---

---

It was in the fall of 1931 that Alan Turing began his studies at Cambridge University. By this time, he had already decided that he would concentrate on mathematics.

In the spring of 1935, Alan Turing took a class on Foundations of Mathematics given by Max Newman. That class included the proof of Gödel's Incompletenss Theorem and a discussion of the Entscheidungsproblem. It was around this time that Turing spent a lot of time thinking about Computable Numbers.

In April of 1936, Alan Turing gave Max Newman a draft of a paper that he was hoping to publish with the title "On Computable Numbers, with an application to the Entscheidungsproblem." In it, Turing explained that a Computable Number is any number that can be computed to any desired degree of accuracy in a finite number of steps by any computer. (In those days, the meaning of the word "computer" was different than what we normaly think of today. At that time, a computer was a real person who was given written instructions with steps to follow when performing calculations using an adding machine. In fact, newspapers carried ads seeking to hire computers.) In his paper, Turing described an Automatic Computing Machine (later to be known as the Turing Machine) as an automated version of exactly such a human computer; except that, instead of having written instructions in English, he had to introduce the concepts of machine states and data read and written on a paper tape.

Newman was very impressed with Turing's draft of his paper. The implications were indeed significant. For one thing, it showed that all numbers are not computable. In fact, most numbers--and in fact, almost all numbers--are not computable!!! Furthermore, the paper explained how a Universal Computing Machine could be designed that could do anything that any other Automatic Computing Machine could do. And, last but not least, it also answered the Entscheidungsproblem in the negative.

---

Meanwhile, at Princeton University in New Jersey, Alonzo Church had been busy for the past few years inventing a new formal system in mathematical logic which he called λ-calculus. In 1936 he was already giving lectures on it. In that same year, he became the Founder of a new journal that he named Journal of Symbolic Logic.

Also in that same year, Alonzo Church made a great discovery! He found out that, using the λ-calculus that he invented, he could solve the Entscheidungsproblem. He decided to write this up in a paper entitled A Note on the Entscheidungsproblem. (In time, this became known as Church's Theorem).

Wanting to share this good news with his friend Max Newman at Cambridge, Church mailed a copy of his paper A Note on the Entscheidungsproblem to him and explained that he planned to publish it in the first issue of his new Journal of Symbolic Logic. (Church and Newman became friends when Max Newman visited Princeton University in 1928-1929.)

---

Max Newman received the letter from Alonzo Church while he was still reading the draft of Alan Turing's paper.

When Alan Turing found out about this, he was devastated!! This clearly meant that all the time that Turing spent on writing his paper was wasted! He spent so much time and so much effort on trying to solve the Entscheidungsproblem--which he knew would be historically significant--and someone else beat him to it! There was absolutely no sense in publishing his paper now!

Max Newman, however, felt that the approach that Turing used was so different from Church's that Turing's paper was still worth publishing. There were discoveries in the paper by Turing that were not in the one by Church, and vice-versa. Newman encouraged Turing to finish his paper and publish it as soon as he could.

Turing did finish his paper, and included a reference to Church's paper in the introduction, where he explained that what he called "computable" was called "effectively calculable" by Church. He submitted his paper for publication to the Proceedings of the London Mathematical Society where it was received on May 28, 1936. Turing then added an appendix to this paper, where he compared the concepts he presented with those of Church, and this was received on August 28.

Meanwhile, on May 31, Max Newman wrote letters to Alonzo Church and to the London Mathematical Society explaining that he felt that Turing's approach to resolving the Entscheidungsproblem was different enough from that of Church that it merited publication.

Alan Turing's paper was published in two parts in the November and December, 1936, issues of the Proceedings of the London Mathematical Society. It was later republished in its entirety in the December, 1937 issue.

Max Newman suggested to Alan Turing that he continue his graduate studies under the direction of Alonzo Church at Princeton University. Turing followed this advice, and attended Princeton from September, 1936 through July, 1938 at which time he received his Ph.D. in Mathematics with Alonzo Church as his Ph.D. advisor. After that, he returned to Cambridge, England.

---