General Topic Doubt Theory of Computation: Recursive And Recursively Enumerable Languages

Question

State True or False with a reason .Is Recursive lang. turing recognizable

Comments

@kumar.dilip you can refer here,

https://www.geeksforgeeks.org/recursive-and-recursive-enumerable-languages/

---

Is Recursive lang. turing recognizable

If the language is recursive, then there exist a turing machine which can accept/reject that language. recursive languages are subset of recursively enumerable. so given turing recognizable means it is recursively enumerable. so question becomes is recursive languages are recursively enumerable - True every recursive language is recursively enumerable.

The first comment explains reverse part, if it is a turing recognizable it means it may or may not turing decidable. i.e. A recursively enumerable language may or may not recursive language. As there are languages which recursively enumerable but not recursive.

---

Difference b/w Recognizers and Deciders :-

• On all input:
  • A Decider MUST halt (in Accept or Reject state)
  • A Recogizer MAY or MAY NOT halt on some strings 

For more Refer this link: https://www.radford.edu/nokie/classes/420/Chap3-Langs.html

Answer 1

Turing recognizable is  equvalent to recursive ennumrable.