538 views
3 votes
3 votes
As per Rice's theorem if the problem is undecidable then it can be RE but Not REC or Not RE. So basically if something is not decidable,then it can be either RE but not REC or Not RE.

But i have also read that RE consists is Semi decidable problems,which may include semi decidable as well as decidable.

But my question is what is scope of semi decidable.By looking at above two variations ,the first one of Rice's theorem says that it is undecidable and the other one says that it is semi decidable.

So do we consider semi decidable as undecidable also?Can i say every undecidable is Not RE?or the other way every semidecidable is undecidable?

1 Answer

3 votes
3 votes
Undecidable - NOT RE (No mechanical solution exists at all for such problems)
Semi-decidable - RE (Solution exists for "Yes" case)
Decidable - REC (HTM exists for all such problems)

Related questions

3 votes
3 votes
1 answer
1
rahul sharma 5 asked Aug 1, 2017
1,965 views
Semidecidable means RE or only but NOT REC? Can i say every semi decidable is undecidable?
–2 votes
–2 votes
0 answers
2
Anmol Verma asked Dec 4, 2016
925 views
How to solve decidable problems and undecidable problems.......Its getting very difficult to understand....??
1 votes
1 votes
1 answer
3
Xylene asked Jul 15, 2017
1,088 views
From rice theorem, I know that it is not recursive. But can someone prove that ? Or atleast give some intuitive proof?