Question

Describe in detail the difference between computable and uncomputable functions?

Answer 1

Computable functions:-(decidable)

-->Computable function means there exists some algorithm that computes an answer (or output) to any instance of the problem (or for any input to the function) in a finite number of simple steps.

--->Ex:-the integer increment operation

                  f(x)=x+1

--->It should be intuitive that given any integer x, we can compute x+1 in a finite number of steps. since x is a finite,it may be represented by a finite string of digits. Using addition operation we can clearly compute another string of digits representing the integer equivalent to x+1.

Examples:-

1)Compute the greatest common divisor of a pair of integers.

2)computing the least common multiple of a pair o integers.

3)finding the shortest path between a pair of nodes in a finite graph.

-->Proving computability:-

To show that a function is computable by describing a procedure and proving that the procedure always terminates and always produces the correct answer. It is enough to provide a convincing argument that such a procedure exists finding the actual procedure is not necessary(but often helps to make the argument more convincing.

------------------------------------------------------------------------------------------------------------------------------------------

Uncomputable functions:-(uncomputable or undecidable)

-----> A non computable is a function for which there is no algorithm that can be used to solve it.

                                    (or)

---->means that there exists no algorithm that can compute an answer or output for all inputs in a finite number of simple steps.(undecidable simply means non-computable in the context of a decision problem,whose answer (or output) is either "true" or "false").

--->Example:-

Halting problem:- Given a description of turing machine and its initial input,determine whether the program,when executed on this input,ever halts(completes). The alternative is that it runs forever without halting.

The halting problem is about seeing if a machine will ever come to a halt when a certain input is given to it or if it will finish running. This input itself can be something that keeps calling itself forever which means that it will cause the program to run forever.

--->other example:-determining whether a computer program loops forever on some input.

-->proving uncomputability:-

To show that a problem is not computable,we need to show that no algorithm exists that solves the problem. Since there are an infinite number of possible procedures,we cannot just list all possible procedures and show why each one does not solve the problem. Instead,we need to construct an argument showing that if there were such an algorithm it would lead to a contradiction.