Undecidability

Question

Is it so that compliment of undecidable problems (not rec) in the decidability table are always not re as compliment of not rec is not re?

Comments

yes true

---

No. "non-halting" problem is not recursive (also not r.e.) and its complement halting problem is r.e. If a problem is not recursive but r.e., then its complement will be not r.e.

---

@Arjun sir, thank you :) got it!

---

I havenot got

"non-halting" problem is not recursive (also not r.e.) and its complement halting problem is r.e.

any example regarding this?

If a problem is RE and it's complement is also RE

then problem will be recursive. Hence decidable.

right? 

---

@sreshtha yes true. But actually in my question it should be 're but not rec' instead of just ' not rec' as Arjun sir said.

---

ok

but ur question was undecidable problem

RE is not undecidable problem, I think

It is partially decidable or semidecidable problem

I meant to say complement of non RE is non RE

right?

---

Undecidable=not decidable but partially decidable . undecidable and not re=not even partially decidable.compliment of non RE can be non RE or re but not rec.

---

^Undecidable=not decidable but either partially decidable or not even partially decidable. 

---

yes, sorry

---

http://www.cs.columbia.edu/~aho/cs3261/Lectures/L18-Undecidable_Problems.html