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.

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

Start Free Trial

No credit card required