A computational problem is a problem that is expressed sufficiently precisely that it is possible to attempt to build an algorithm to solve it. However, this doesn’t mean that the attempt needs to be successful. However, when there is an algorithm that solves every instance of the problem, we call the problem computable.
A computational problem can be modelled as a mathematical function:
- The inputs of the problem are the domain of the function
- Any outputs of the problem are members of the co-domain of the function
- The desired relationship between inputs and outputs is modelled by the function mapping each member of the domain to a single member of the co-domain.
A mathematical function associates each element from a set called the domain to a single element from a set called the co-domain. All co-domain elements that are associated to some domain element form together the range of the function. Thinking in terms of ADTs, a mathematical function is a (usually infinite) Map of key-value pairs: the domain is the set of all keys, the co-domain is the set of all possible values, and the range is the set of all actual values in the Map. A Python function computes the output for a given input, but a mathematical function, lie a Map, doesn’t compute anything: it just ‘stores’ the associations between the domain and the co-domain elements.
When a function models a computational problem, the function is essentially a set of input-output pairs such that for each valid input, i.e. that satisfies the pre-conditions, there will be exactly one output associated. The domain is the set of all possible valid inputs, the range is the set of all outputs and the co-domain is the set of all possible values for the output type.
A computational problem can be described as computable if it is possible to build an algorithm that solves any instance of the problem in a finite number of steps. More rigorously, we can define a computable problem as follows:
A computational problem f (i.e. a mathematical function) is a computable problem if and only if there is a deterministic Turing Machine M such that for every member x of f‘s domain, if f(x) = y then Turing Machine M halts on input x, after a finite number of steps, with output y. In other words, if there is a Turing Machine that, with some suitable encoding of the function’s domain and co-domain writes on the tape the correct output for the given input and then halts.