Some vocabulary:
- vollständig (Adjektiv) = complete
- unvollständig (Adjektiv) = incomplete
- die Unvollständigkeit (Substantiv) = incompleteness
- der Satz (Substantiv) = theorem(1)
- 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
1st incompleteness theorem:
Any sufficiently powerful recursive formal system is either contradictory or incomplete.
2nd 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:
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.