Editing Computability (section)

== Problems ==

A central idea in computability is that of a ('''computational''') '''[[computational problem|problem]]''', which is a task whose computability can be explored.

There are two key types of problems:
* A [[decision problem]] fixes a set ''S'', which may be a set of strings, natural numbers, or other objects taken from some larger set ''U''. A particular '''instance''' of the problem is to decide, given an element ''u'' of ''U'', whether ''u'' is in ''S''. For example, let ''U'' be the set of natural numbers and ''S'' the set of prime numbers. The corresponding decision problem corresponds to [[primality testing]].
* A [[function problem]] consists of a function ''f'' from a set ''U'' to a set ''V''. An instance of the problem is to compute, given an element ''u'' in ''U'', the corresponding element ''f''(''u'') in ''V''.  For example, ''U'' and ''V'' may be the set of all finite binary strings, and ''f'' may take a string and return the string obtained by reversing the digits of the input (so f(0101) = 1010).
Other types of problems include [[search problem]]s and [[optimization problem]]s.

One goal of computability theory is to determine which problems, or classes of problems, can be solved in each model of computation.