1
GATE CSE 2005
MCQ (Single Correct Answer)
+2
-0.6
Consider three decision problems $${P_1},$$ $${P_2}$$ and $${P_3}.$$ It is known that $${P_1}$$ is decidable and $${P_2}$$ is un-decidable. Which of the following is TRUE?
A
$${P_3}$$ is decidable if $${P_1}$$ is reducible to $${P_3}$$
B
$${P_3}$$ is in-decidable if $${P_3}$$ is reducible to $${P_2}$$
C
$${P_3}$$ is un-decidable if $${P_2}$$ is reducible to $${P_3}$$
D
$${P_3}$$ is decidable if $${P_3}$$ is reducible to $${P_2}'s$$ complement
2
GATE CSE 2001
MCQ (Single Correct Answer)
+2
-0.6
Consider the following problem $$X.$$ Given a Turing machine $$M$$ over the input alphabet $$\sum , $$ any state $$q$$ of $$M$$ And a word $$w\,\,\varepsilon \,\,\sum {^ * ,} $$ does the computation of $$M$$ on $$w$$ visit the state $$q''$$

Which of the following statements about $$X$$ is correct?

A
$$X$$ is decidable
B
$$X$$ is undecidable but partially decidable
C
$$X$$ is undecidable and not even partially decidable
D
$$X$$ is not a decision problem
3
GATE CSE 1991
MCQ (Single Correct Answer)
+2
-0.6
Which one of the following is the strongest correct statement about a finite language over some finite alphabet $$\sum ? $$
A
It could be un-decidable
B
It is Turing-machine recognizable
C
It is a regular language
D
It is a context-sensitive language
4
GATE CSE 1990
MCQ (More than One Correct Answer)
+2
-0.6
It is decidable whether:
A
An arbitrary Turing machine halts after 10 steps.
B
A Turing machine prints a specific letter.
C
A Turing machine computes the product of two numbers.
D
None of the above.
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12