MCQ IN COMPUTER SCIENCE & ENGINEERING

Detailed explanation-1: -A language L is recursively enumerable/Turing recognizable if there is a Turing Machine M such that L(M) = L. A language L is decidable if there is a Turing machine M such that L(M) = L and M halts on every input. Thus, if L is decidable then L is recursively enumerable.

Detailed explanation-2: -Equivalently, a formal language is recursive if there exists a total Turing machine (a Turing machine that halts for every given input) that, when given a finite sequence of symbols as input, accepts it if it belongs to the language and rejects it otherwise. Recursive languages are also called decidable.

Detailed explanation-3: -A Turing machine M is said to decide a language L if L = L(M) and M halts on every input. L is said to be Turing-recognizable (or simply recognizable) if there exists a TM M which recognizes L. L is said to be Turing-decidable (or simply decidable) if there exists a TM M which decides L.

Detailed explanation-4: -Explanation: A language is recursive if there exists a turing machine such that it halts i.e. accepts if the input belongs to the language else rejects. It is better called Turing decidable language.

Detailed explanation-5: -The correct answer is “option 4". If there exists a Turing machine that accepts every string of the language and does not accept any string that is not in the language then, the language is recursively enumerable language.