What is the Entscheidungsproblem?

---

Entscheidungsproblem is a German word that means "Decision problem."

In the year 1900, the famous German mathematician David Hilbert presented a list of problems at a speech he gave at an International Congress of Mathematicians in Paris. The tenth problem on that list could be paraphrased as follows:

David Hilbert also gave a speech at another International Congress of Mathematicians, this time in 1928 at Bologna, in which he posed three questions. The third of these questions was the following:

It is this third question that David Hilbert posed in 1928 that is usually meant by Hilbert's Entscheidungsproblem, although the word Entscheidungsproblem is sometimes used to refer to Hilbert's tenth problem of 1900 as well.

---

So what does the question "Is mathematics decidable?" really mean?

Perhaps it would be a good idea to rephrase the question "Is mathematics decidable" as follows:

While mathematicians all over the world were struggling to answer this Entscheidungsproblem, a young mathematician by the name of Kurt Gödel came up with the following very remarkable result: There are statements in mathematics that are true but can never be proved!

As remarkable as this Gödel's Incompleteness Theorem really is, it still does not answer the Entscheidungsproblem. After all, you can still imagine the existence of that universal algorithm that we're looking for. Then, if we apply it to one of those "true but unprovable" statements that Gödel was talking about, then it'll just tell us "no, you can't prove this!" That doesn't mean the statement isn't true. Maybe it's true, or maybe it's not; but at least we would know that we can't prove it.

So, does there exist a universal algorithm that we can apply to any statement in mathematics just to see if it's provable, or not?

In 1936, Alonzo Church and Alan Turing, working independently, proved that such a universal algorithm is not possible. Alonzo Church did it using his λ-calculus, while Alan Turing did it using his Turing Machine.

So, the answer to David Hilbert's third question of 1928 is this: No! Mathematics is not decidable!

---

Church and Turing proved that mathematics is not decidable. However, we can limit the entire field of mathematics just to a specific subfield of it, and ask the question whether that subfield is decidable. The question would then be: Given this set of axioms, can an algorithm be designed to tell me if any statement in this area of mathematics is provable from the axioms? The answer is yes, and an example of such is the Presburger arithmetic, named after Mojżesz Presburger.

---

The Entscheidungsproblem as it specifically applies to Hilbert's tenth problem presented in Paris in 1900 was resolved by Yuri Matiyasevich in his Ph.D. Dissertation written in 1970. Here too, the answer is "No, there can be no universal algorithm for solving Diophantine Equations."

---