retagged by
14,291 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

1 votes
1 votes
$1. \ \text{Emptiness problem for Turing machine is undecidable.}$

$2. \text{The problem is decidable because the input is running on M for only 100 steps, and at 100th step if the present state is q then} < M, w, q> \text{is in $L_2$ else its not} $

$3. \text{This is not trivial property of TM as a L(M) can be REC or RE.}$

$4. \text{Using Rice's theorem, we know that Any non-trivial property of the LANGUAGE recognizable by a Turing machine (recursively enumerable language) is undecidable.}$

$ \ | L_{yes} |= 21$ and $L_{no} = \phi. \text{Hence } L_2 \text{ is undecidable.}  $

$A$ is the correct option.
edited by
0 votes
0 votes
L1: It is the emptiness problem for REL, which is undecidable.

L2: It is state entry problem, which is reducible to hailting problem but with finite length, hence it will be decidable.

L3: Since the language has a TM it is definitely a REL. But here we have no information about, whether the TM halts on every string or not, or there exists a TM that halts on every string of L. Hence we cannot say if the language is recursive or not.

L4: We can not say if L has exactly 21 members. It may keep looping around for some input. Hence it is undecidable.
0 votes
0 votes
All credit to Deepak sir

 

L1 is undecidable, by rice theorem part 2, it is undecidable as it is non monotonic property

L2 is decidable as check for 100 steps, it is accept accepts, else reject

L3 is undecidable as It is non trivial property , by rice theorem, it is undecidable

L4 is undecidable as it is also non trivial, hence by rice theorem it is undecidable.
Answer:

Related questions

18 votes
18 votes
7 answers
2
Arjun asked Feb 12, 2020
13,350 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,734 views
If $P = 3$, $R = 27$, $T = 243$, then $Q + S =$ ________$40$$80$$90$$110$