O'Reilly logo

Introduction to Automata Theory, Formal Languages and Computation by Shyamalendu Kandar

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

10

Computability and Undecidability

Introduction

According to the Church thesis, the algorithm of any computational procedure can be represented by the Turing machine (TM). Are there some problems for which there are no algorithms to solve the problem? This question divides the set of problems into two parts, namely, decidable and undecidable. If there exists an algorithm to solve a problem, the problem is called decidable; otherwise, it is undecidable. Before discussing undecidability, it is needed to know about the languages accepted by the TM.

10.1  TM Languages

A string w is said to be accepted by a TM if it gets halt(H). What happens if it does not get halt? It may happen that for the current state q and the current input symbol ∈ Σ, no ...

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