• Register
    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 580

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
  • Questions
    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 580
  • Unanswered
    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 580
  • Tags
    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 580
  • Categories
    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 580
  • Users
    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 580
  • Exams Taken
    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 580
  • Exam List
    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 580

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

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

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

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

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

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 = \{<M,w> : \text{on input w, Turing Machine M eventually enters the reject state}\}

\small L3 : \{<M,q> :\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

asked Sep 7, 2019 by gbeditor-2 (72,840 points)
reshown Sep 8, 2019 by gbeditor-2

2 Answers

0 votes
 
Best answer

L1 : Undecidable 

 

image

 

L2 : Undecidable

 

image

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)
0 votes

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 bhargavakapilpro20 (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
Answer:

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

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

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
...