Self Doubt

Question

Are Turing Recognizable and Turing Acceptable languages same? What is their relationship with recursive enumerable and recursive language?

Answer 1

yes

both are recursively enumerable

recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptableor Turing-recognizable )are those for which given a string of that language, Turing machine halts on accept state if string is present in language and it may or may not halt on reject state if string is not in language so for "No" TM can loop forever

Recursive languages are those for which give a finite set of input TM halts on both "yes" (if string is present in lang.) and "no"(if string is not in language) these are also called as Turing machine Decidable language

Answer 2

Turing recognisable , Turing acceptable , Turing computable , partially decidable and semi decidable all are synonyms of recursively enumerable language.In simple terms if we say , such turing machines can accept a string if the string comes under the corresponding recursively enumerable language.But in case of rejection of a string , the operation of Turing machine may or may not end..In other words the machine may halt or hang in case of rejection of string in case the language concerned is recursively enumerable but not recursive language.

Whereas Turing decidable , or simply decidable , is a synonym for recursive languages. The turing machine of such machine has halting property i.e. in case of both acceptance or rejection of a string under recursive class of language , the Turing machine will halt definitely [ hence termed as Turing decidable ].

Recursive language is a subset of recursively enumerable language .i.e. every recursive language is also recursively enumerable but the converse is not true all the times [Converse is not true for those languages which are recursively enumerable but not recursive].I hope u understand these basic terms.

Answer 3

Turing recognizable language nothing but language on which turing machine run and say yes or no same ways as recursive enumerable languages of u->v wherere u is (VUT)+  and v is (VUT)*

.REL::

There is no membership algorithm exist for such languages and turing machine may halt and say yes it is present in our languages range or say no or go to infinite.

RL::

It is subset of REL but there exist a membership algorithm on it and it always halt such turing machine for subset of REL is subset os machine of TM is HTM.