TOPICS
Search

Decision Problem


Does there exist an algorithm for deciding whether or not a specific mathematical assertion does or does not have a proof? The decision problem is also known as the Entscheidungsproblem (which, not so coincidentally, is German for "decision problem").

Using the concept of the Turing machine, Turing showed the answer to be negative for elementary number theory. J. Robinson and Tarski showed the decision problem is undecidable for arbitrary fields.


See also

Church's Theorem, Gödel's First Incompleteness Theorem, Gödel's Second Incompleteness Theorem, Peano Arithmetic, Presburger Arithmetic

Explore with Wolfram|Alpha

References

Church, A. "A Note on the Entscheidungsproblem." J. Symb. Logic 1, 1936.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 1100 and 1136, 2002.

Referenced on Wolfram|Alpha

Decision Problem

Cite this as:

Weisstein, Eric W. "Decision Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DecisionProblem.html

Subject classifications