1 votes 1 votes what is the difference between recursive enumerable and not recursive enumerable(not partially decidable)? Theory of Computation theory-of-computation decidability + – Mk Utkarsh asked Jan 2, 2018 Mk Utkarsh 900 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply joshi_nitish commented Jan 2, 2018 reply Follow Share Recursively enumerable languages are those for which TM exists need not be halting TM(but it should halt for every strings in language). Non-Recursively enumerable languages are those for which no TM exists. 0 votes 0 votes Mk Utkarsh commented Jan 2, 2018 reply Follow Share agree on the Non- Recursively enumerable part but for RE what do you mean by "it should halt for every string in language" if it halts for every string in the language then it is decidable right? because if it is halting for every string then it can either reject or accept. 0 votes 0 votes joshi_nitish commented Jan 2, 2018 reply Follow Share @Mk Utkarsh "it should halt for every string in language" i have said it should halt for every string in language, this doesn't means that language is decidable, to be decidable it should halt on every string in universe(either the string is from language or from outside the language) 2 votes 2 votes Mk Utkarsh commented Jan 2, 2018 reply Follow Share oh yeah thanks :) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes recursive enumerable language is semi-decidable (partially decidable) language.i.e there exist a turing machine , non recursive enumerable language is undecidable language i.e turing machine dose not exist. abhishekmehta4u answered Apr 24, 2018 abhishekmehta4u comment Share Follow See all 0 reply Please log in or register to add a comment.
