1,310 views
0 votes
0 votes
is every SEMI DECIDABLE an RE but not RECURSIVE??

plz help me with this.

2 Answers

Best answer
3 votes
3 votes

For a language $L$

If there is some Turing Machine that accepts every string in $L$ and rejects every string not in $L$, then $L$ is a decidable language.

if there is some Turing machine that accepts every string in $L$ and either rejects or loops on every string not in $L$, then $L$ is Semi-decidable or recursive enumerable(RE)  or computably enumerable (CE).

Semi-decidable means "Recursive enumerable".

Undecidable means "Not REC"

Semi-Decidable And Undecidable means "RE but Not REC"

selected by
2 votes
2 votes

I hope,the concept is clear .

Related questions

3 votes
3 votes
2 answers
3
3 votes
3 votes
1 answer
4