Entscheidungsproblem  

From The Art and Popular Culture Encyclopedia

Jump to: navigation, search

Related e

Wikipedia
Wiktionary
Shop


Featured:

In mathematics and computer science, the Template:Lang (Template:IPA-de, German for "decision problem") is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928. The problem asks for an algorithm that takes as input a statement of a first-order logic (possibly with a finite number of axioms beyond the usual axioms of first-order logic) and answers "Yes" or "No" according to whether the statement is universally valid, i.e., valid in every structure satisfying the axioms. By the completeness theorem of first-order logic, a statement is universally valid if and only if it can be deduced from the axioms, so the Template:Lang can also be viewed as asking for an algorithm to decide whether a given statement is provable from the axioms using the rules of logic.

See also




Unless indicated otherwise, the text in this article is either based on Wikipedia article "Entscheidungsproblem" or another language Wikipedia page thereof used under the terms of the GNU Free Documentation License; or on research by Jahsonic and friends. See Art and Popular Culture's copyright notice.

Personal tools