Entscheidungsproblem and Unvollständigkeitssatz

Question

This is a question about specialized vocabulary in mathematics/logic, and also in history of mathematics/logic.

The first term is used by Hilbert in his 1928 work, but in Gödel's later work, the same thing is referred to as Unvollständigkeitssatz ("incompleteness theorem"). For today's German CS (computer science) researchers, it seems Unvollständigkeitssatz is more commonly used, and Entscheidungsproblem ("decision problem") is still understood, but not necessarily associated with das Halteproblem (which seems to be more common after Turing's work on automata). On the other hand, for English CS researchers, Entscheidungsproblem is usually the only word they are familiar with.

Interestingly, when looking at the German Wikipedia, there is no entry for Entscheidungsproblem, but there is one for Gödelscher Unvollständigkeitssatz, and the entry about Hilbert uses Gödelscher Unvollständigkeitssatz. When looking at the English Wikipedia, one readily finds an entry for Entscheidungsproblem.

How come Entscheidungsproblem is no longer used? Does it sound old?

Is it possible that Hilbert asked an Entscheidung question, and Gödel responded by saying that mathematics is unvollständig? Meaning, Unvollständigkeit would be something that prevents for Entscheidbarkeit. Is that possible in German?

Answer 1

Some vocabulary:

• vollständig (Adjektiv) = complete
• unvollständig (Adjektiv) = incomplete
• die Unvollständigkeit (Substantiv) = incompleteness
• der Satz (Substantiv) = theorem⁽¹⁾
• der Unvollständigkeitssatz (Substantiv, singular) = incompleteness theorem
• die Unvollständigkeitssätze (Substantiv, plural) = incompleteness theorems
• entscheiden (Verb) = to decide
• die Entscheidung (Substantiv) = decision
• das Problem (Substantiv) = problem
• das Entscheidungsproblem (Substantiv, singular) = decision problem
• die Entscheidungsprobleme (Substantiv, plural) = decision problems
• anhalten, halten (Verben) = to halt, to stop (verbs)
• der Halt (Substantiv) = halt, stop (nouns)
• das Halteproblem = halting problem, stop problem

(1) "Satz" is "theorem" only in mathematics. There are more than 20 way to translate Satz into German, depending on context, see https://dict.leo.org/englisch-deutsch/Satz.

So, the terms Unvollständigkeitssatz, Entscheidungsproblem and Halteproblem mean three different subjects:

---

Gödels Unvollständigkeitssätze

Gödel's incompleteness theorems

Article in German Wikipedia: Gödelscher Unvollständigkeitssatz
Article in English Wikipedia: Gödel's incompleteness theorems

1^st incompleteness theorem:

Any sufficiently powerful recursive formal system is either contradictory or incomplete.

2^nd incompleteness theorem:

Any sufficiently powerful consistent formal system can not prove its own consistency.

Both theorems are theorems, not problems. The topic of both theorems are formal systems, like mathematics itself.

Gödel first theorem says:

In all useful formal systems (like mathematics itself):
either ...

• there are assertions, which can be proven to be both, true and false. This would mean, that the system (i.e. mathematics itself) is contradictory.

... or ...

• there are true assertions (i.e. theorems), which can not be proven whether they are true or false. This would mean, that the system is incomplete.

(or both, i.e. contradictory and incomplete)

The second theorem says:

If there is a formal system (like mathematics itself), that is consistent (i.e. it does not contain any contradictories), then this consistency can not be proven from within this system.
In other words:
If mathematics is consistent, then it is not possible to prove that mathematics is consistent.

---

Entscheidungsprobleme

decision problems

Article in German Wikipedia: Entscheidungsproblem redirects to Entscheidbar
Article in English Wikipedia: Entscheidungsproblem

This is NOT a theorem. It is a class of problems.

Decision problems are problems that appear in set theory. Here is a generic description of this sort of problems:

You have a set that contains elements. Some of this elements have a certain property. You have to decide for each element, if it has this property or not. The problem is the question, if there is an algorithm that is able to meet this decision for every given element.

An example for a decision problem is this:

Given is the set of all positive integers. Some of them are prime. Is it possible to find an algorithm, that can decide for any positive integer if it is prime or not?

This example has a solution, i.e., it is possible to tell for each positive integer, whether it is prime or not.

---

Halteproblem

halting problem

Article in German Wikipedia: Halteproblem
Article in English Wikipedia: Halting problem

This is another example for a decision problem.

Given is the set of all possible combinations of computer programs and their inputs. In some of this combinations the program will halt at some time. (In all other combinations the program will run forever.) Is it possible to find an algorithm, that can decide for any combination of program and input if the program will halt?

It can be proven, that this problem has no solution, i.e. there are combinations of computer programs and inputs where it is not possible to tell if the program will halt sometimes or if it will run forever.

---

None of the words feel old or outdated. They just feel mathematical, and they are still used in mathematics and computer science.

The reason, why there is no distinct article about »Entscheidungsproblem« in German Wikipedia is just because it has another title. There are some more redirects that lead to the same article:

• Entscheidungsproblem (decision problem)
• Entscheidbarkeit (decidability)
• Unentscheidbares Problem (undecidable problem)
• Entscheidbar (decidable) (this is the target of the redirects)

So, in German you have four links to reach this information, while in English the only way to reach the article is Entscheidungsproblem. No other English title redirects to this article.

Answer 2

I've studied maths and computers, and both Entscheidungsproblem and Unvollständigkeitssatz are used.

Note that the nuance is different: decision problem (Entscheidungsproblem) means "is there an algorithm that can decide the following question?", so that's what you'd normally use if discussing the Halteproblem, properties of formal grammars etc. There's tons of those, and of course it's often in the context of a concrete for of simplified computer which is used to construct the proof.

On the other hand, incompleteness theorem (Unvollständigsatz) refers to the question "can a particular proof system, usually one associated with arithmethic, prove every statement that is true, and disprove every statement that's false?" If your proof system can't, then the proof system is "incomplete".

Now every proof system can be formulated as an algorithm, and every model of computation can be formulated as something that looks similar to a proof system, so those two are equivalent, but they still have different flavours.