O'Reilly logo

Formal Languages and Automata Theory by K.V.N. Sunitha

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required