7
Undecidability and Computability
- Decidability and computability are the basic factors to analyse the algorithms.
In this chapter, we try to understand the importance and procedure to check whether the problem is solvable or not. As we know, computers have capabilities and limitations, and it becomes essential to have a mechanism by which we can identify an unsolvable problem, so that the problem can be altered or simplified before finding an algorithmic solution.
In the computability theory and the computational complexity theory, a decision problem is like a question in some formal system with a yes or no answer, depending on the values of some input parameters. For example, In two given numbers x & y, does x evenly divide y?’ is a decision ...
Get Formal Languages and Automata Theory now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
