The Gateway to Computer Science Excellence
+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 by Boss (25.2k points) | 169 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)
by Boss (43.3k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,654 questions
56,169 answers
94,307 users