15 votes 15 votes Which of the following statement is FALSE? All recursive sets are recursively enumerable. The complement of every recursively enumerable sets is recursively enumerable. Every Non-empty recursively enumerable set is the range of some totally recursive function. All finite sets are recursive. The complement of every recursive set is recursive. Theory of Computation tifr2010 theory-of-computation recursive-and-recursively-enumerable-languages + – makhdoom ghaya asked Oct 11, 2015 • edited May 15, 2018 by Milicevic3306 makhdoom ghaya 2.5k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply arch commented Jan 2, 2018 reply Follow Share what does option c means? 4 votes 4 votes Bikram commented Jul 22, 2019 reply Follow Share (B) Because RE language are not closed under complement. 0 votes 0 votes Please log in or register to add a comment.
Best answer 15 votes 15 votes (B) The complement of every recursively enumerable sets is recursively enumerable. Because RE language are not closed under complement. Umang Raman answered Oct 8, 2015 • edited Jun 15, 2018 by Milicevic3306 Umang Raman comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments VS commented Aug 10, 2017 reply Follow Share @Bikram sir Can you please explain option c? Thanks in advance :) 0 votes 0 votes Bikram commented Aug 10, 2017 reply Follow Share @VS Every Non-empty recursively enumerable set is the range of some totally recursive function. This means , the elements( or members ) of non empty Recursively enumerable set are total recursive functions . like , if S is a set , and If x is a member (or element) of S, then we use the notation x ∈ S . we can write this as , S = {x} similarly here , Non empty Recursively enumerable = { all possible output values of total recursive functions } . ------------ There are some discussion about this statement : " The set of total recursive functions is not recursively enumerable ." Please read these threads : https://math.stackexchange.com/questions/111773/are-total-recursive-functions-recursively-enumerable?rq=1 https://math.stackexchange.com/questions/762988/clarification-of-the-argument-for-the-set-of-total-recursive-functions-not-being?rq=1 https://math.stackexchange.com/questions/133319/a-revisit-to-the-question-can-total-recursive-functions-be-recursively-enumerat?rq=1 10 votes 10 votes commenter commenter commented Jul 22, 2019 reply Follow Share Every Non-empty recursively enumerable set is the range of some totally recursive function. "Every Non-empty recursively enumerable set" - Every non-empty recursive enumerable language, "totally recursive function" - "total function of some recursive language. In short, the sentence means, There is a recursive language which can be many-to-one reducible to all the non-empty recursive enumerable language. Remember that many-to-one reduction means that there is a total function which maps one language to other, the mapping necessarily is not an injection (one-one). 2 votes 2 votes Please log in or register to add a comment.