GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 44

Answer 1

A,B,C are correct options Doubt is at option D.

Note:- We know every(All RE Language also) language is subset of $\sum$* .

We know $\sum$* is a Regular language and it is Decidable too.

And  we know RE languages (not all RE, because Recursive Languages are subset of RE language and Recursive Languages are decidable because there exist a HTM) are Undecidable. 

Every RE language is subset of $\sum$* which is Decidable.{from above note}

Hence, we can say that Subset of every decidable langiuage is not decidable so,Option D is incorrect.

Please correct me if  i am wrong.

 

Answer 2

Explanation for option D:

Suppose a language L1 is decidable and there exists a language L2 which is a subset of language L1. Since L1 is decidable, there exists a machine M1 which halts and accepts any string w ∈ L1. Suppose a machine M* exists which halts and accepts the string w if M1 halts and rejects the string w, practically being the machine which accepts the complement of language L1.

Now if Language L2 is also decidable that means there exists a machine M2 which stops/halts for every string in L2 and either accepts or rejects it. That means there should also exist a halting turing machine M** which should halt and accept the strings from the complement of language L2.

But since L2 ⊆ L1, therefore L1’ ⊆ L2’, and saying “a halting turing machine M** exists for L2’ because a halting turing machine M* exists for its subset L1’ ” would be incorrect because option only talks about the decidability of L1 and L1’ does not accounts for all the strings in L2’ , so the remaining strings of L2’ may or may not have a halting turing machine for them.

Basically, ∃M2 → ∃M**, and since we are saying existence of M** is not implied by the premise of the option, therefore ∼∃M** → ∼∃M2.

Therefore subset of a decidable language need not be decidable.