Recognizable vs Decidable

What is difference between “recognizable” and “decidable” in context of Turing machines?

Answer

A language is Recognizable iff there is a Turing Machine which will halt and accept only the strings in that language and for strings not in the language, the TM either rejects, or does not halt at all. Note: there is no requirement that the Turing Machine should halt for strings not in the language.

A language is Decidable iff there is a Turing Machine which will accept strings in the language and reject strings not in the language.

Perhaps this link will be helpful: http://kilby.stanford.edu/~rvg/154/handouts/decidability.html

Attribution
Source : Link , Question Author : metdos , Answer Author : Aryabhata

Leave a Comment