A decision problem asks for a yes-or-no answer for every input. In computational complexity , inputs are finite words
over a fixed finite alphabet
(Watrous 2009). A decision procedure is an
algorithm that halts on every input and returns the
correct answer.
In mathematical logic , the historical decision problem known as the Entscheidungsproblem asks whether an algorithm
can decide whether an arbitrary expression in a specified axiomatic
system has a proof (Church 1936, p. 41). The name
Entscheidungsproblem is German for "decision problem."
Church (1936, p. 41) and Turing (1937, pp. 259-263) proved that the decision problem for first-order logic has no decision
procedure . Turing's proof uses the concept of a Turing machine . The general first-order theory of
arbitrary fields is also undecidable
(Robinson 1949, p. 113).
See also Church's Theorem ,
Computational Complexity ,
Decision Procedure ,
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 , 40-41, 1936. https://doi.org/10.2307/2269326 . Robinson,
J. "Definability and Decision Problems in Arithmetic." J. Symb. Logic 14 ,
98-114, 1949. https://doi.org/10.2307/2266510 . Turing,
A. M. "On Computable Numbers, with an Application to the Entscheidungsproblem."
Proc. London Math. Soc. 42 , 230-265, 1937. https://doi.org/10.1112/plms/s2-42.1.230 . Watrous,
J. "Quantum Computational Complexity." In Encyclopedia of Complexity
and Systems Science (Ed. R. A. Meyers). New York: Springer, pp. 7174-7201,
2009. https://doi.org/10.1007/978-0-387-30440-3_428 . Wolfram,
S. A
New Kind of Science. 1109
and 1136 ,
2002. Referenced on Wolfram|Alpha Decision Problem
Cite this as:
Weisstein, Eric W. "Decision Problem."
From MathWorld https://mathworld.wolfram.com/DecisionProblem.html
Subject classifications
