Computable and Non-Computable Functions
7 Computable Functions
Computable functions are the basic objects of study in Theory of Computation. Computable functions are the functions that can be calculated using a mechanical calculation device given unlimited time and memory space. Also any function that has an algorithm is computable. Each computable function f takes a fixed finite number of natural numbers as arguments. The computable function f returns an output for some inputs.For some inputs, it may not return an output. Due to this, a computable function is a paertial recursive function. If the computable function is defined for all possible arguments, it is called a total computable function or total recursive function. The notation f(x1, x2, .........xk) indicates that the partial function f is defined on arguments x1, x2, .........xk. We say that a function f on a certain domain is said to be computable, if there exists a Turing machine that computes the value of f for all arguments in its domain. A function is uncomputable if no such Turing machine exists. The basic characteristic of a computable function is that there is a finite procedure or algorithm telling how to compute the function. The characterisitics of a computable function are as follows:
1. There must be exact instructions (ie, a program, finite in length).
2. If the procedure is given a k tuple x in the domain of f, then after a finite number of steps, the procedure must terminate and produce f(x).
3. If the procedure is given a k-tuple x which is not in the domain of f, then the procedure must never halt, or it may get stuck at some point.
Following are some examples for computable functions:
1. Each function with a finite domain. eg. Any finite sequence of natural numbers.
2. Each constant function f : Nk → N, f(n1, n2,.....nk) = n.
3. Addition f : N2 → N, f(n1, n2) = n1, n2.
4. The function which gives the list of prime factors of a number.
5. The gcd of two numbers is a computable function.
8 Non-Computable Functions
The real numbers are uncountable so most real numbers are not computable. Most subsets of natural numbers are not countable. A non-computable function corresponds to an undecidable problem and it consists of a family of instances for which there is no computer program that given any problem instance as input terminates and outputs the required answer after a finite number of steps. For an undecidable problem, it is impossible to construct a single algorithm that always leads to a correct yes/ no answer. We say that a function f on a certain domain is said to be non-computable, if no Turing machine exists that computes the value of f for all arguments in its domain. Examples for undecidable problems (non-computabel functions) are halting problem, post correspondence problem.