The document Computable and Non-Computable Functions Computer Science Engineering (CSE) Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Theory of Computation.

All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

**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_{1}, x_{2}, .........x_{k}) indicates that the partial function f is defined on arguments x_{1}, x_{2}, .........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_{1}, n_{2},.....n_{k}) = n.

3. Addition f : N^{2} → N, f(n_{1}, n_{2}) = n_{1}, n_{2}.

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.

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!

18 videos|43 docs|39 tests