Computable & Non-Computable Functions | Theory of Computation - Computer Science Engineering (CSE) PDF Download

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(x₁, x₂, .........x_k) indicates that the partial function f is defined on arguments x₁, x₂, .........x_k. 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 : N^k → N, f(n₁, n₂,.....n_k) = n.
3. Addition f : N² → N, f(n₁, n₂) = n₁, n₂.
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.