Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 3 down vote favorite
1

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

share|improve this question

1 Answer

up vote 7 down vote accepted

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

share|improve this answer
For a language to be recognizable, you need there to be a machine which accepts all strings in the language, and also fails to accept all strings not in the language. With your definition, all languages are recognizable by the always-accept machine. – Chris Eagle Mar 8 '11 at 18:15
@Chris: Was editing... Thanks! – Aryabhata Mar 8 '11 at 18:16
Great to know, thnks, very helpful! had that question in mind and i cldnt find a real difference – user23259 Jan 19 '12 at 21:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.