Decidability and Undecidability

 

Decidability and Undecidability

Decidability

It is also known as solvability and tractable problems.if problem have a solution then this is solvable. If the solution is restricted to the set {Yes,No} then this problem is known as decision problem because the solution of the problem is in yes or no.

For Example problem or question is earth move round the sun?

Answer is yes ,no one say no because that is universal truth. That problem is decidable problem.

For example Problem or question India mother tongue language is hindi?

Answer is yes,no one say no. that problem is decidable problem.

For example Problem or question is You are police officer?

Answer is no, that problem is also decidable.

If a problem is solved based on some algorithm then it is known as decidable problem.

Undecidable Problem

That problem is also known as unsolvable and untractable problem.if the problem has both the answer sometimeas "yes" and sometimes "no" the problem is undecidable. That is called unsolvable because  some time answer is yes sometime no . Not specific yes or no . that type of problem is called untractable problem.No algorithm exit for that type of problem .

A problem is said to be decidable if that satisfy condition

Its language is  recursive(yes or no ,not loop)

It has solution or answer(algorithm).

The problem that do not satisfy the above condition are called undecidable or unsolvable problem.

Main undecidable problem are

Halting problem.

post corresspondance problem.

Main decidable problem is 

Use membership(CYK) algorithm to check whether w∊ L(G) or not. so that problem is decidable.

Example of undecidable problem

 For example problem is Will tomorrow be a rainy day?

Answer is Do not know it may or may not. so that problem solution is unsolvable .No algorithm for that solution that is undecidable problem.