110 views
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
+1
I is correct, but II is incorrect
0
only $I$ correct .$\text{HINT_:Membership Algorithm}$

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.

selected
0
So, all r.e. problems can be reduced to halting problem?
0
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.
0
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?

1