TOC (Decidable or Not)

Question

Which is correct?

I) All recursive enumerable language would be recursive, if halting problem is decidable

II) For any CFG, it is undecidable whether or not a particular non terminal "X" in G is reachable

a) I is correct but II is incorrect

b) II is correct but I is incorrect

c) Both are correct

d) Both are incorrect

Comments

I is correct, but II is incorrect

---

only $I$ correct .$\text{HINT_:Membership Algorithm}$

Answer 1

For statement 1 , we need to know about the reduction theorem :

In   X  <_m   Y  , if Y is known to be RE then X will be RE . Also if Y is known to be REC , then X will also be REC . Hence all problems reducible to halting problem will be RE as per the normal case as halting problem is RE but not REC . 

But if Y which is a halting problem in this case were decidable , it means Y is recursive and hence any problem reducing to Y will be recursive specifically rather than simply RE . 

Hence in this case , all recursively enumerable languages will become recursive language .Hence statement 1 is true.

For statement 2 , we know that the given problem has algorithm to solve and hence decidable . In this first we have to identify the start symbol , then identify the set of non terminals that are part of production of this start symbol ; directly or indirectly . Hence we can say whether a given non terminal in the context free grammar G is reachable or not.

Hence the given problem is decidable and this makes statement 2 false. Thus A) should be the correct option.

Comments

So, all r.e. problems can be reduced to halting problem?

---

Its just like NP complete thing . If we can reduce one NP complete problem , say 0/1 knapsack to P domain , then P will become NP . In other words all other NP complete problems will come in P as well .

So should be the case with this also.

---

NP-Complete problem is different -- because that is how NP-Complete class is defined. Any problem in NP can be reduced to any NPC problem. But is it the same for halting problem? I mean given any r.e. problem can we reduce it to halting problem?