The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
is every SEMI DECIDABLE an RE but not RECURSIVE??

plz help me with this.
asked in Theory of Computation by Junior (741 points) | 223 views

RE(but not recursive) itself means Semi Decidable. Means TM can decide only its yes instances.
If TM can decide No instances as well, which means the language is decidable(Recursive).

2 Answers

+2 votes
Best answer

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"

answered by Boss (21.8k points)
selected by
+2 votes

I hope,the concept is clear .

answered by Active (3.5k points)
So halting problem is semi-decidable or undecidable?

According to Rice theorem,

Every non trivial problem on RE language is undecidable.

So halting problem is undecidable.

And not "semi-decidable"?
I think halting problem is semidecidable . Becz we can make a turing machine for halting problem . So it is recurcive ennum language .

can u give an example ?

There was a question asked in gate 1996 . see question 3.7. and see answer 3.7 option 'a'


^ are you believing solutions given in GATE books?

Meanwhile halting problem is semi decidable and any semi decidable problem which is not decidable is undecidable. Or you can say some undecidable problems are semi decidable.
But many people do not consider semi-decidable, instead semi-decidable is considered as undecidable like Halting Problem.
GATE answers are not made by "public voting".
Well, I know that Sir!

I am not believing on gate books....I have seen this topic in many places.

Even in Wikipedia it is written that the halting problem is undecidable!

Please give it a look.


If you still have any queries this is the proof given in KLP Mishra book. See topic 10.5

Undecidable means, there is no T.M that always say YES(if string belongs to language) or NO(if string doesn't), for every input string.
Decidable means for every i/p string we can decide whether it belongs to language or not.
Now, Semi-decidable means, if the string belongs to language then it will say YES but if string doesn't belong then it will not necessarily say NO, as T.M might run forever..
so Semi-decidable is a subset of Undecidable. But any times, people call it undecidable only bcoz, we can not decide it always.
my friennd thank a lot
Actually saying semi-decidable as a subset of undecidable is technically wrong because it includes all decidable problems too.

So halting problem(HP) is semi-decidable or undecidable?

Both Undecidable and Semi decidable. Undecidable because HP is not Decidable(recursive) and Semi decidable because HP is RE.

Semi decidable means RE, and Undecidable means Not REC. So, Semi decidable and Undecidable would mean "RE but Not REC"

Actually, All the 3-4 Standard Undecidable problems are Semi decidable and Undecidable(i.e. RE but Not REC) Blank tape problem, State entry problem, Post correspondence problem etc


I hope,the concept is clear .

In the Diagram(Screenshot of the Note book Page), everything was going well. You yourself have written there that "Semi decidable is a Superset of Decidable". But At last you have come to the conclusion that "Every Semi decidable is RE but Not REC". 

Not correct conclusion.

You yourself have came to the conclusion that semi decidable are REC but not RE in your answer. I have also written the same thing.

As you can see from the vein diagram

REC is a subset of RE

TTM is a subset of TM

Decidable problems are subset of semi decidable problems. There are some semi decidable problems that are not Decidable i.e. they are RE(Recursive Enumerable)  but not REC(Recursive).

So, my conclusion is correct.

So all decidable problems are semi decidable but converse is not true.

I have mentioned nowhere that semi decidable is a subset or superset of undecidable. I have just shown the relation between decidable and semi decidable problem. "semi-decidable as a subset of undecidable is technically wrong" is correct .

This is the relation between the three types if I am not wrong.

Yes, that relationship is correct. But in your answer the third column heading should be "not even semi-decidable" and not "undecidable".

Related questions

0 votes
0 answers
0 votes
0 answers
0 votes
1 answer

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

47,139 questions
51,387 answers
66,699 users