Computable and non-computable problems in TOC

Computable Problems –
You are familiar with many problems (or functions) that are computable (or decidable), meaning 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.A simple example is 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 finite, it may be represented by a finite string of digits. Using the addition method (or algorithm) we all learned in school, we can clearly compute another string of digits representing the integer equivalent to x + 1.

Yet there are also problems and functions that that are non-computable (or undecidable or uncomputable), meaning 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”).

Non-Computable Problems –
A non-computable is a problem for which there is no algorithm that can be used to solve it. Most famous example of a non-computablity (or undecidability) is the Halting Problem. Given a description of a 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 of an uncomputable problem is: determining whether a computer program loops forever on some input. You can replace “computer program” by “Turing machine or algorithm”if you know about Turing machine.

Proving Computability or Non-Computability –
We can show that a problem 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).

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.

The core of our argument is based on knowing the Halting Problem is noncom- putable. If a solution to some new problem P could be used to solve the Halting Problem, then we know that P is also noncomputable. That is, no algorithm exists that can solve P since if such an algorithm exists it could be used to also solve the Halting Problem which we already know is impossible.The proof technique where we show that a solution for some problem P can be used to solve a different problem Q is known as a reduction.A problem Q is reducible to a problem P if a solution to P could be used to solve Q. This means that problem Q is no harder than problem P, since a solution to problem Q leads to a solution to problem P.

Some Examples On Computable Problems –
These are four simple examples of computable problem:

1. Computing the greatest common divisor of a pair of integers.
2. Computing the least common multiple of a pair of integers.
3. Finding the shortest path between a pair of nodes in a finite graph.
4. Determining whether a propositional formula is a tautology.

Some Examples On Computable Problems – State Entry Problem.
Consider the problem of determining if a string ‘w’ is given to some Turing machine ‘M’ will it enter some state ‘q'(where q belongs to set of all states in Turing machine M and string w is not equal to empty string). Is it computable or non-computable?

Explanation –
We show the State Entry Problem is non-computable by showing that it is as hard as the Halting Problem, which we already know is non-computable.

State Entry Problem is asking us on given string w if we start from initial state of Turing machine will it reach to a state q. Now this state entry problem can be converted to halting problem. Halting problem is whether our Turing machine ever halts and state entry problem is asking same thing whether this Turing machine halts at some state q if we give string w as input to the Turing machine M. So the state entry problem is non-computable as we converted it to halting problem which we already know is non-computable problem. So in this way we can prove non-computability.