Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

# TOC-grand test-Q12

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177
+1 vote

Consider the following languages

$\small L1 =\{ < M> : \text{Turing Machine M accept} \in \text{ in an even number of moves}\}$

$\small L2 = \{ : \text{on input w, Turing Machine M eventually enters the reject state}\}$

$\small L3 : \{ :\text{ the Turing machine M enters the state q on some input }\}$

Which of the above languages are DECIDABLE ?

(A) Only L2

(B) Only L1

(C) Only L3

(D) None of them

reshown Sep 8, 2019

L1 : Undecidable

L2 : Undecidable

L3 : Undecidable

Let L denote the language in question. If L were decidable, then we would be able to check whether the language of any given Turing machine M is empty by running L’s decider on (M,qaccept) This would contradict Rice’s theorem, which asserts that every nontrivial property of the language of a Turing machine (such as emptiness) is undecidable.

Hence Option D

answered Sep 11, 2019 by (91,540 points)

ANS D (not sure)

L2 and L3 are UD , halting problem they are.

L1 should also be UD as we dont have fixed steps.

answered Sep 8, 2019 by (14,660 points)
but in L2, input is fixed. so cant we check it on a single input?
It is same as halting prob. as on input we may enter into loop and never stop. Or maybe sometime stop also. Therefore UD.
ok ok, i thought if it is a particular input then it might be decidable.
it that case, D should be the answer