# Entscheidungsproblem vs. Unvollständigkeitssatz (soft question)

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?

• 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? Feb 28 '17 at 23:12
• 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. Mar 1 '17 at 0:50
• There is however a German Wikipedia entry for Enscheidbar (decidable) 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. Mar 1 '17 at 3:13
• 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. Mar 1 '17 at 3:17
• @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. Mar 1 '17 at 8:46