Crack
GATE
C
G
Topic
Turing machines and undecidability
Theory of Computation
0
/ 9 done
Questions per paper
All
MCQ
MSQ
NAT
2015 to 2026. Point at a year to read it.
0
1
2015
2019
2021
2023
2025
2026
Show as a table
Year
All
MCQ
MSQ
NAT
2015
1
1
0
0
2018
0
0
0
0
2019
1
1
0
0
2020
1
1
0
0
2021
1
0.5
0.5
0
2022
1
0
1
0
2023
0
0
0
0
2024
0
0
0
0
2025
0
0
0
0
2026
0.5
0.5
0
0
1
CS 2026 Set 2 · 1 mark · MCQ · Easy
Which one of the following statements is equivalent to the following assertion?
Turing machine
M
decides the language
L
⊆
{
0
,
1
}
∗
\text{Turing machine } M \text{ decides the language } L \subseteq \{0,1\}^*
Turing machine
M
decides the language
L
⊆
{
0
,
1
}
∗
2
CS 2022 · 2 marks · MSQ · Moderate
Which of the following is/are undecidable?
3
CS 2021 Set 1 · 1 mark · MSQ · Easy
Let
⟨
M
⟩
\langle M \rangle
⟨
M
⟩
denote an encoding of an automaton
M
M
M
. Suppose that
Σ
=
{
0
,
1
}
\Sigma = \{0, 1\}
Σ
=
{
0
,
1
}
. Which of the following languages is/are NOT recursive?
4
CS 2021 Set 1 · 2 marks · MCQ · Hard
For a Turing machine
M
M
M
,
⟨
M
⟩
\langle M \rangle
⟨
M
⟩
denotes an encoding of
M
M
M
. Consider the following two languages.
5
CS 2020 · 2 marks · MCQ · Moderate
Which of the following languages are undecidable? Note that
⟨
M
⟩
\langle M \rangle
⟨
M
⟩
indicates encoding of the Turing machine
M
M
M
.
6
CS 2019 · 2 marks · MCQ · Moderate
Consider the following sets:\n\nS1. Set of all recursively enumerable languages over the alphabet
{
0
,
1
}
\{0, 1\}
{
0
,
1
}
\nS2. Set of all syntactically valid C programs\nS3. Set of all languages over the alphabet
{
0
,
1
}
\{0, 1\}
{
0
,
1
}
\nS4. Set of all non-regular languages over the alphabet
{
0
,
1
}
\{0, 1\}
{
0
,
1
}
\n\nWhich of the above sets are uncountable?
7
CS 2015 Set 2 · 1 mark · MCQ · Easy
Consider the following statements.
8
CS 2015 Set 2 · 1 mark · MCQ · Moderate
Consider two decision problems
Q
1
,
Q
2
Q_1, Q_2
Q
1
,
Q
2
such that
Q
1
Q_1
Q
1
reduces in polynomial time to
3
-SAT
3\text{-SAT}
3
-SAT
and
3
-SAT
3\text{-SAT}
3
-SAT
reduces in polynomial time to
Q
2
Q_2
Q
2
. Then which one of the following is consistent with the above statement?
9
CS 2015 Set 3 · 2 marks · MCQ · Moderate
Language
L
1
L_1
L
1
is polynomial time reducible to language
L
2
L_2
L
2
. Language
L
3
L_3
L
3
is polynomial time reducible to
L
2
L_2
L
2
, which in turn is polynomial time reducible to language
L
4
L_4
L
4
. Which of the following is/are true?