DECIDABILITY OF A PROBLEM

A problem (p1) is said to be decidable if there exists an algorithm or a haulting turing machine for that problem.

Generally we decide whether the problem is decidable or not by comparing it with the other known problem(p2) whose decidability is known.

ie.. if there exists some algorithm or process by which (p1) can be converted to (p2) and it is well known about the decidability of the (p2) then we can say that problem (p1) is also decidable.

And we have to make sure that problem the result of (p1) = result of(p2)

This process can be extended to chain of problems.

All the problems in the chain has same result

Eg:  It is well known that Haulting problem in turing machine is un-decidable.

A haulting problem can be converted to post correspondence problem and post corresponcence problem is also undecidable.

In addition post correspondance problem can be converted to ambigious problem in context free grammers.

Therefore ambiguity problem in context free grammers is also undecidable.

 

Contributor's Info

Created:
0Comment