retagged by
14,279 views
31 votes
31 votes

Which of the following languages are undecidable? Note that $\left \langle M \right \rangle$ indicates encoding of the Turing machine M.

  • $L_1 = \{\left \langle M \right \rangle \mid  L(M) = \varnothing \}$
  • $L_2= \{\left \langle M,w,q \right \rangle \mid  M \text{ on input } w \text{ reaches state } q \text{ in exactly } 100 \text{ steps}\}$
  • $L_3= \{\left \langle M \right \rangle \mid L (M) \text{ is not recursive}\}$
  • $L_4= \{\left \langle M \right \rangle \mid L(M) \text{contains at least $21$ members}\}$
  1. $L_1$, $L_3$, and $L_4$ only
  2. $L_1$ and $L_3$ only
  3. $L_2$ and $L_3$ only
  4. $L_2$, $L_3$, and $L_4$ only
retagged by

7 Answers

Best answer
23 votes
23 votes

We can answer this question just using Rice's theorem which states as follows:

Any non-trivial property of the LANGUAGE recognizable by a Turing machine (recursively enumerable language) is undecidable

Trivial property of a set$:$ For all instances of the set the property evaluates to True or for all instances of the set the property evaluates to False. i.e., without inspecting the “given instance” we can say whether it has the property or not. For example, “Language accepted by a TM is recursively enumerable”. This is always true as any language accepted by a TM is called recursively enumerable by definition (it can also be recursive or context-sensitive or context-free or regular or finite also).

Non-trivial property of a set$:$ For some instances of the set the property evaluates to True and for some it evaluates to False. For example,: “Language accepted by a TM is context free language”. This is true if the language can also be accepted by some $\textsf{PDA}$ but is false if no such $\textsf{PDA}$ exists like for $L = \{ww \mid w \in \{0,1\}^*\}.$ 

$L_1 = \{\left \langle M \right \rangle \mid  L(M) = \varnothing \}$

  • $L_{1}$ is emptiness problem and is non-trivial because we can have two Turing machines $M_1$ and $M_2$ with $L(M_1) = \varnothing$ and $L(M_2) = \{0\}$ (something non-empty). 
  • So, $L_1$ is undecidable.

$L_3= \{\left \langle M \right \rangle \mid L (M) \text{ is not recursive}\}$

  • $L_3$ is also describing a non-trivial property (of the language of Turing machines) as the language of not all the Turing machines is recursive. For example, we can have a Turing machine for halting problem and its language is recursively enumerable but not recursive.

$L_4= \{\left \langle M \right \rangle \mid L(M) \text{contains at least $21$ members}\}$

  • $L_4$ is also describing a non-trivial property as we can have two Turing machines $M_1$ and $M_2$ with say $L(M_1) = \{0\}$ and $L(M_2) = \{0^{2n}\mid n \geq 0\},$ where the property holds for $L(M_2)$ but not for $L(M_1).$  So, $L_4$ is also undecidable.

$L_2= \{\left \langle M,w,q \right \rangle \mid  M \text{ on input } w \text{ reaches state } q \text{ in exactly } 100 \text{ steps}\}$

  • This is actually a property of Turing machine and not its language. Obviously this is a non-trivial property (but of $\textsf{TM}$ and not its language and hence Rice’s theorem is not applicable). Here, we have to check if the given $\textsf{TM}$ on given input $w$ reaches state $q$ in exactly $100$ steps – certainly decidable as we just need to monitor the working of Turing machine for $100$ steps which should happen in a finite amount of time. But if instead of $100$ steps the question is modified to reaching state $q$ ever, then the problem becomes state reachability problem and there is no guarantee that we can answer this problem in finite amount of time (we can answer “yes” but not necessarily “no”), and the problem becomes undecidable (but is still semi-decidable).

So A is correct.

https://gatecse.in/rices-theorem/

selected by
41 votes
41 votes

Correct Option: A

$L_1$ is famous emptiness problem-Undecidable.

$L_2$ is decidable as we can run the TM for 100 steps and see if it reaches state q.

$L_3$ is undecidable as given a TM we won't be able to say whether the language generated is recursive or not.. Therefore undecidable

$L_4$ is undecidable because you cannot say with surety that L(M) has at least 21 members. What if the TM keeps on processing for some input.How long will you wait to decide.It may or may not halt.

edited by
6 votes
6 votes

We can use Rice's Theorem to answer such question. Let's build up to it.

 


 

Let's say $P$ is a function, such that if a language $L$ satisfies some given property; then $P(L)=1$.

Otherwise, $P(L)=0$

This is a pretty intuitive Boolean notation.

 


 

Now, Rice's Theorem states that every non-trivial property of a Recursively Enumerable languages is undecidable.

Introduction to Automata Theory by Hopcroft and Ullman, 3rd Edition, page 397.


 

What is a non-trivial property of RE languages?

A property of RE languages is said to be non-trivial, if there exists Turing Machines $M_1$ and $M_2$, such that $P(L(M_1))=1$ and $P(L(M_2))=0$

In plain English, this means that the property of an RE language is non-trivial, if there exists some Turing Machine whose languages have that property, and there also exists some Turing Machine whose languages don't have that property.


 

Now let's use Rice's Theorem.

$L_1$ is undecidable because we can construct a TM that acceps nothing, and we can construct a TM that acceps something.

Similarly; $L_3$ and $L_4$ are also undecidable.

$L_2$ is decidable ONLY because of the fact that we've been mentioned the number of steps.

Otherwise it would be undecidable, too.

Each "step" in a Turing Machine would take a finite amount of time. Let's say it takes maximum $x$ units of time. So, for $L_2$ we only have to observe the Turing Machine for $100x$ units of time. We can't fall in infinite loop here; hence, decidable.

 

Option A
3 votes
3 votes

Any non-trivial property of the LANGUAGE recognizable by a Turing machine (recursively enumerable language) is undecidable

Brief explanation of what is trivial and non trivial property of a language.

Trivial property => For all instances the property evaluates to be True. Ex: If language accepted by a TM in context free language. It is always true irrespective of language chosen.

Non Trivial property => For some instances the property evaluates to be True and for some False. Ex: If language accepted by a TM in context free language. It is always true irrespective of language chosen.

$L_{1}$ is emptiness problem. 

Why undecidable? Emptiness problem of TM is non trivial.

$L_{3}$ is not recursive 

Why undecidable? Non trivial property of TM as some of it will be recursive and some only REL not recursive.

$L_{4}$ is L(M)contains at least 21 members

Why undecidable? Property than L(TM) at least 21 members is non trivial. Some will have while others don't.

$L_{2}$ M on input w reaches state q in exactly 100 steps. Here its not typical state entry problem   We cannot apply part 1 of Rice Theorem here as its not property of a language. Its decidable as we can run TM for 100 steps and get result in finite time.

If $L_{2}$ was M on input w reaches state q in anytime after 100 steps, it will be undecidable.

So A is correct.

https://cs.stackexchange.com/questions/22106/how-do-you-classify-properties-as-trivial-and-non-trivial

https://gatecse.in/rices-theorem/

Answer:

Related questions

18 votes
18 votes
7 answers
2
Arjun asked Feb 12, 2020
13,338 views
Consider the following language.$L = \{{ x\in \{a,b\}^*\mid}$number of $a$’s in $x$ divisible by $2$ but not divisible by $3\}$The minimum number of states in DFA that ...
9 votes
9 votes
3 answers
4
Arjun asked Feb 12, 2020
5,731 views
If $P = 3$, $R = 27$, $T = 243$, then $Q + S =$ ________$40$$80$$90$$110$