Share this entry

Share this page

decision problem

Syllabification: de·ci·sion prob·lem

Definition of decision problem in English:

noun

Logic
The problem of finding a way to decide whether a formula or class of formulas is true or provable within a given system of axioms.
Example sentences
  • He worked on mathematical logic solving certain cases of the decision problem for the first order predicate calculus, simplified results of Bernays, and worked on ideas of Post, Gödel and Church.
  • In a lecture given at Harvard during 1939-40 Tarski said: -… the solution of the decision problem in its most general form is negative.… [Surely] many mathematicians experienced a profound feeling of relief when they heard of this result.
  • This is a representation of ‘all logical and physical relations between variables representing the decision problem being examined.’

Origin

1930s: translating German Entscheidungsproblem.

Definition of decision problem in:

Share this entry

Share this page

 

What do you find interesting about this word or phrase?

Comments that don't adhere to our Community Guidelines may be moderated or removed.

Get more from Oxford Dictionaries

Subscribe to remove adverts and access premium resources

Word of the day Noel
Pronunciation: nəʊˈɛl
noun
Christmas…