Register

TOC Semi decidable problems

827 views
3 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 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)
Voting & Accepting an answer helps improve the community
← Previous · Doubt in access link...Next → · Computer Networks: B...
← Previous in category · turing machineNext in category → · TOC Languages Differ...
Position:
Show:

Related questions

3 3 votes
1 answers 1 answer
2.7k
2.7k views
rahul sharma 5 asked Aug 1, 2017
2,736 views
TOC Semi Decidable
Semidecidable means RE or only but NOT REC? Can i say every semi decidable is undecidable?
–1 –1 vote
0 0 answers
1.2k
1.2k views
Anmol Verma asked Dec 4, 2016
1,218 views
General TOC decidable problems
How to solve decidable problems and undecidable problems.......Its getting very difficult to understand....??
1 1 vote
1 1 answer
1.5k
1.5k views
Xylene asked Jul 15, 2017
1,521 views
Proof of whether a TM accepts epsilon is semi decidable
From rice theorem, I know that it is not recursive. But can someone prove that ? Or atleast give some intuitive proof?
8 8 votes
0 0 answers
1.3k
1.3k views
Manu Thakur asked Sep 9, 2017
1,276 views
Decidable problems concerning Turing machine
Can someone please verify my answers on the following given languages?Please note that RE=Recursive Enumerable, LBA=Linear Bounded Automata, and TM=Turing Machine$\text{H...