Computation problem - Definition and Overview

In computability theory a computation problem is determining whether or not there exists a computation procedure or algorithm for a class S of questions requiring a non-Boolean value (i.e., a value from {1, 2, 3...}). These are also known as what-questions and differ from the class of questions requiring a Boolean value (see decision problem). For example, the computation problem for the class of questions "What is the sum of two positive integers x and y?" is computable because there exists a mechanical procedure, namely addition, which allows us to determine for any x and any y the value of x + y (or the value of "What is the sum of two positive integers x and y?"). In other words, the function <math>f(x,y) = x + y<math> is computable.

The class of functions that are computable is countably infinite whereas the class of all functions is uncountable. This suggests that there are uncomputable functions. Refer to the list of undecidable problems for examples.