11
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 5
    $\begingroup$ 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? $\endgroup$ – Joshua Grochow Feb 28 '17 at 23:12
  • 1
    $\begingroup$ 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. $\endgroup$ – Frank Mar 1 '17 at 0:50
  • $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Mar 1 '17 at 3:13
  • $\begingroup$ 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. $\endgroup$ – Frank Mar 1 '17 at 3:17
  • $\begingroup$ @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. $\endgroup$ – Emil Jeřábek Mar 1 '17 at 8:46
18
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks! Exactly what I was looking for. Can you point to which of Hilbert's questions Unvollständigkeitssatz answers? $\endgroup$ – Frank Mar 1 '17 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.