0 votes 0 votes This language, L = { <M,w> / M is a TM,w is a string and M does not halt on string w } is not recursively enumerable ...right ??? Theory of Computation theory-of-computation decidability recursive-and-recursively-enumerable-languages + – vignesh asked Apr 21, 2017 • retagged Jul 4, 2017 by Arjun vignesh 368 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply AnilGoudar commented Apr 21, 2017 reply Follow Share Recursive language : Language accepted by a halting TM. When a string belonging to Recursive language is given to halting TM/ TM , the TM will say that the given string is present in the Language and halts. When a string not in Recursive language is given to halting TM, the TM will say that the given string is not present in Language and halts. Recursively Enumerable language: Language accepted by TM. When a string belonging to Recursive language is given to TM , the TM will say that the given string is present in the Language and halts. When a string not in Recursive language is given to TM, the TM will not halt instead it enters a loop. Since M does not halt on w, and language L is defined over this TM, the language accepted by this TM is Recursively Enumerable language. I think L is recursively enumerable language. Correct me if iam wrong. 0 votes 0 votes Kapil commented Apr 21, 2017 reply Follow Share Yes, it is non RE . 2 votes 2 votes AnilGoudar commented Apr 21, 2017 reply Follow Share @Kapil, Please explain 0 votes 0 votes Arjun commented Apr 22, 2017 reply Follow Share This is the complement of halting problem. Any TOC book should have reason why this is not r.e. If this problem is r.e., then halting problem becomes decidable. 4 votes 4 votes AnilGoudar commented Apr 22, 2017 reply Follow Share Thank you. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes it is recursive because there is an answer for the string that whether it will halt or not ; but in recursive enumrable language we know only if it will be acceptable and there is no decidebility for yes or no . akankshadewangan24 answered Apr 30, 2017 akankshadewangan24 comment Share Follow See all 0 reply Please log in or register to add a comment.