The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+5 votes
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
asked in Theory of Computation by Boss (11.4k points) | 85 views
I is correct, but II is incorrect
only $I$ correct .$\text{HINT_:Membership Algorithm}$

1 Answer

+3 votes
Best answer

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.

answered by Veteran (98.7k points)
selected by
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?

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

36,194 questions
43,647 answers
42,929 users