<p>The two words do not refer to the same thing. Hilbert's <em>Entscheidungsproblem</em> was the question whether there is an algorithm that decides the universal truth of first-order logical sentences, which was answered negatively by Turing in his famous 1936 paper "On Computable Numbers, with an application to the <em>Entscheidungsproblem</em>". The word literally means <em>decision problem</em>. I assume that the word is no longer used since it refers to a problem that has been solved. In English it may still be more common due to its prominent use in the title of Turing's paper.</p>

<p>Gödels <em>Unvollständigkeitssatz</em> is his incompleteness theorem, stating that no consistent arithmetic theory is complete, in particular it can not prove its own consistency. This answered negatively a different question of Hilbert, viz. the second of his 23 famous problems, which was to prove the consistency of the axioms of arithmetic.</p>

CC BY-SA 3.0
2017-03-01T08:40:15.640Z
2017-03-01T15:41:01.200Z
2017-03-01T15:41:01.200Z
Jan Johannsen
<p>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 <em>Unvollständigkeitssatz</em> ("incompleteness theorem"). For today's German CS researchers, it seems <em>Unvollständigkeitssatz</em> is more commonly used, and <em>Entscheidungsproblem</em> ("decision problem") is still understood, but not necessarily associated with <em>das Halteproblem</em> (which seems to be more common after Turing's work on automata). On the other hand, for English CS researchers, <em>Entscheidungsproblem</em> is usually the only word they are familiar with.</p>

<p><strong>Note</strong>: the words are not the same, and it could be argued that Hilbert's question about <em>deciding</em> was answered in the negative for a particular case by Gödel's statements about <em>incompleteness</em>, so that <em>incompleteness</em> demolishes <em>decision</em> in general. </p>

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

<p>How come <em>Entscheidungsproblem</em> is no longer used in German? </p>

CC BY-SA 3.0
2017-02-28T23:12:28.613Z
Interesting - for today's English CS researchers, when reading about history it is more frequently referred to as the Entscheidungsproblem - so much so that I had never heard the term Unvollstandigkeitssatz before this question! Can you give a rough translation of the two terms into English?
Joshua Grochow
CC BY-SA 3.0
2017-03-01T00:50:47.517Z
Yes, but surprisingly, the German Wikipedia does not have an entry for _Entscheidungsproblem_, but _Gödelscher Unvollständigkeitssatz_, is a Wikipedia entry (in German), and the entry about Hilbert uses _Gödelscher Unvollständigkeitssatz_.
Frank
CC BY-SA 3.0
2017-03-01T03:13:24.283Z
There is however a German Wikipedia entry for Enscheidbar (decidable) https://de.wikipedia.org/wiki/Entscheidbar. My German is poor, but browsing Wikipedia suggests that Unvollständigkeitssatz is indeed what is called the "incompleteness theorem" in English. This is related to the Entscheidungsproblem, but it does not solve it. The Entscheidungsproblem asks whether there is a procedure that decides if a given statement in first order logic is provable. The incompleteness theorem (Unvollständigkeitssatz) does not answer this question.
Sasho Nikolov
CC BY-SA 3.0
2017-03-01T03:17:11.317Z
Does it not answer in the negative, by showing that at least for arithmetic, such a procedure cannot be devised? So there is not a single procedure that will always be able to decide if any statement in first order logic is provable, given axioms.
Frank
CC BY-SA 3.0
2017-03-01T08:46:18.340Z
@Frank The Ent... refers to logic without extra axioms. The undecidability of such doesn't directly follow from the incompleteness theorem as proved by Godel, because he deals with a theory that's not finitely axiomatizable.
Emil Jeřábek
CC BY-SA 3.0
2017-03-01T09:03:03.733Z
@SashoNikolov sorry I saw only now that your comment essentially already says what I wrote in my answer.
Jan Johannsen
<lo.logic><computability><ho.history-overview>
Entscheidungsproblem vs. Unvollständigkeitssatz (soft question)
Frank
# Entscheidungsproblem vs. Unvollständigkeitssatz (soft question)

(Asked by: username_0 on 2017-02-28)

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 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.

**Note**: the words are not the same, and it could be argued that Hilbert's question about *deciding* was answered in the negative for a particular case by Gödel's statements about *incompleteness*, so that *incompleteness* demolishes *decision* in general.

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 in German?

**Tags:** lo.logic, computability, ho.history-overview
> **Comments:**
> **username_1**: Interesting - for today's English CS researchers, when reading about history it is more frequently referred to as the Entscheidungsproblem - so much so that I had never heard the term Unvollstandigkeitssatz before this question! Can you give a rough translation of the two terms into English?  
> **username_0**: Yes, but surprisingly, the German Wikipedia does not have an entry for _Entscheidungsproblem_, but _Gödelscher Unvollständigkeitssatz_, is a Wikipedia entry (in German), and the entry about Hilbert uses _Gödelscher Unvollständigkeitssatz_.  
> **username_2**: There is however a German Wikipedia entry for Enscheidbar (decidable) https://de.wikipedia.org/wiki/Entscheidbar. My German is poor, but browsing Wikipedia suggests that Unvollständigkeitssatz is indeed what is called the "incompleteness theorem" in English. This is related to the Entscheidungsproblem, but it does not solve it. The Entscheidungsproblem asks whether there is a procedure that decides if a given statement in first order logic is provable. The incompleteness theorem (Unvollständigkeitssatz) does not answer this question.  
> **username_0**: Does it not answer in the negative, by showing that at least for arithmetic, such a procedure cannot be devised? So there is not a single procedure that will always be able to decide if any statement in first order logic is provable, given axioms.  
> **username_3**: @Frank The Ent... refers to logic without extra axioms. The undecidability of such doesn't directly follow from the incompleteness theorem as proved by Godel, because he deals with a theory that's not finitely axiomatizable.  
> **username_4**: @SashoNikolov sorry I saw only now that your comment essentially already says what I wrote in my answer.  

---

## 1 answers

### Answer by username_4 on 2017-03-01. Score: 17 | Accepted answer

The two words do not refer to the same thing. Hilbert's *Entscheidungsproblem* was the question whether there is an algorithm that decides the universal truth of first-order logical sentences, which was answered negatively by Turing in his famous 1936 paper "On Computable Numbers, with an application to the *Entscheidungsproblem*". The word literally means *decision problem*. I assume that the word is no longer used since it refers to a problem that has been solved. In English it may still be more common due to its prominent use in the title of Turing's paper.

Gödels *Unvollständigkeitssatz* is his incompleteness theorem, stating that no consistent arithmetic theory is complete, in particular it can not prove its own consistency. This answered negatively a different question of Hilbert, viz. the second of his 23 famous problems, which was to prove the consistency of the axioms of arithmetic.


---

