Decision problem

Summary

A decision problem is a question with a yes or no answer for each of infinitely many inputs, such as "is the number $n$ prime?". Once inputs are written as strings, a decision problem is the same as a formal language: the set of inputs whose answer is yes. Decision problems are the main objects of computability theory and complexity theory. A problem is decidable when an algorithm answers it correctly on every input, and the halting problem is the standard example of an undecidable one.