Log In
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?
in Theory of Computation 197 views

1 Answer

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

2 votes
1 answer
Semidecidable means RE or only but NOT REC? Can i say every semi decidable is undecidable?
asked Aug 1, 2017 in Theory of Computation rahul sharma 5 578 views
–2 votes
0 answers
How to solve decidable problems and undecidable problems.......Its getting very difficult to understand....??
asked Dec 4, 2016 in Theory of Computation Anmol Verma 366 views
1 vote
1 answer
From rice theorem, I know that it is not recursive. But can someone prove that ? Or atleast give some intuitive proof?
asked Jul 15, 2017 in Theory of Computation Xylene 357 views
7 votes
0 answers
I am more interested to know which problems are Recursive Enumerable and which are Non Recursive Enumerable.
asked Sep 9, 2017 in Theory of Computation Manu Thakur 297 views