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).

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 votes

+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"

+2 votes

0

According to Rice theorem,

Every non trivial problem on RE language is undecidable.

So halting problem is undecidable.

+1

I think halting problem is semidecidable . Becz we can make a turing machine for halting problem . So it is recurcive ennum language .

0

can u give an example ?

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

.

+1

^ 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.

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.

0

But many people do not consider semi-decidable, instead semi-decidable is considered as undecidable like Halting Problem.

0

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!

https://en.wikipedia.org/wiki/Halting_problem

Please give it a look.

+1

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.

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.

+2

Actually saying semi-decidable as a subset of undecidable is technically wrong because it includes all decidable problems too.

+1

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)..like Blank tape problem, State entry problem, Post correspondence problem etc

0

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.

0

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.

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.

0

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.

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.5k
- Digital Logic 2.1k
- Programming & DS 4k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 450
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,106 questions

45,608 answers

132,246 comments

49,230 users