chapter

Turing Machines, Decidability and Undecidability PYQs for GATE CS

Solve 6+ Turing Machines, Decidability and Undecidability previous year questions for GATE CS with answers and detailed solutions. Free sample questions below

Try a question

Answer it here to see how it works. Nothing is recorded until you sign in.

Question 1

2026 Slot Set2 PYQ

Which one of the following statements is equivalent to the following assertion? Turing machine M decides the language L \subseteq {0, 1}^{*}

Question 2

2025 Slot Set2 PYQ

Let G_{1}, G_{2} be Context Free Grammars (CFGs) and R be a regular expression. For a grammar G, let L (G) denote the language generated by G . Which ONE among the following questions is decidable?

Question 3

2022 PYQ

Which of the following statements is/are TRUE?

Question 4

2022 PYQ

Which of the following is/are undecidable?

Question 5

2021 Slot Set1 PYQ

For a Turing machine M, ⟨ M ⟩ denotes an encoding of M . Consider the following two languages. L_{1} = {⟨ M ⟩ ∣ M takes more than 2021 steps on all inputs} L_{2} = {⟨ M ⟩ ∣ M takes more than 2021 steps on some input} Which one of the following options is correct?

Question 6

2021 Slot Set1 PYQ

Let ⟨ M ⟩ denote an encoding of an automaton M . Suppose that Σ = {0, 1} . Which of the following languages is/are NOT recursive?

Free preview ends here

Login to view the complete previous-year questions and solutions

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Turing Machines, Decidability and Undecidability PYQs for GATE CS

Solve 6+ Turing Machines, Decidability and Undecidability previous year questions for GATE CS with answers and detailed solutions. Free sample questions below.

Perfect Shuffle and Sequence Permutations

Algorithmic Thinking • String & Sequence Manipulation

Perfect Shuffle & Sequence Permutations

The mathematical backbone of interleaving data — essential for understanding deterministic permutations in programming.

Core Concept Exam Pattern

What you will learn here

The exact definition and mechanics of a perfect shuffle
How to map any element's old index to its new index using a formula
Tracing multiple consecutive shuffles without brute force
Critical edge cases and common off-by-one traps

Intuition: The Two-Half Interleave

The Physical Analogy

Think of a standard deck of cards. A perfect shuffle (also called a Faro shuffle) is not a random mix. It is a strictly deterministic operation.

Step 1: Split

Divide the sequence of $2 n$ elements into two equal halves of size $n$ .

Step 2: Interleave

Alternate picking elements, starting with the first half.

If our sequence is $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]$ :

First half: $[1, 2, 3, 4, 5]$
Second half: $[6, 7, 8, 9, 10]$

Interleaving step-by-step:

Take 1 (from first half)
Take 6 (from second half)
Take 2 (from first half)
Take 7 (from second half) ...and so on.

Result: $[1, 6, 2, 7, 3, 8, 4, 9, 5, 10]$

Notice that the very first element and the very last element never change their positions in this specific type of shuffle.

Turing Machines, Decidability and Undecidability: Solved Questions with Step-by-Step Explanations (6 Problems)

Question 1 · Theory of Computation · 2026_Set2 MCQ

Which one of the following statements is equivalent to the following assertion?

Turing machine M decides the language L \subseteq {0, 1}^{*}

A.
Turing machine $M$ halts on all input strings in ${0, 1}^{*}$
B.
Turing machine $M$ accepts all input strings in $L$
C.
Turing machine $M$ rejects all input strings in ${0, 1}^{*} - L$
D.
Turing machine $M$ accepts all input strings in $L$ and rejects all input strings in ${0, 1}^{*} - L$

Question 2 · Theory of Computation · 2025_Set2 MCQ

Let

G_{1}

G_{2}

be Context Free Grammars (CFGs) and

R

be a regular expression. For a grammar

G

, let

L (G)

denote the language generated by

G

.

Which ONE among the following questions is decidable?

A.
Is $L (G_{1}) = L (G_{2})$ ?
B.
Is $L (G_{1}) \cap L (G_{2}) = \emptyset$ ?
C.
Is $L (G_{1}) = L (R)$ ?
D.
Is $L (G_{1}) = \emptyset$ ?

Question 3 · Theory of Computation · 2022 MSQ

Which of the following statements is/are TRUE?

A.
Every subset of a recursively enumerable language is recursive.
B.
If a language $L$ and its complement $\overline{L}$ are both recursively enumerable, then $L$ must be recursive.
C.
Complement of a context-free language must be recursive.
D.
If $L_{1}$ and $L_{2}$ are regular, then $L_{1} \cap L_{2}$ must be deterministic context-free.

Question 4 · Theory of Computation · 2022 MSQ

Which of the following is/are undecidable?

A.
Given two Turing machines $M_{1}$ and $M_{2}$ , decide if $L (M_{1}) = L (M_{2})$ .
B.
Given a Turing machine $M$ , decide if $L (M)$ is regular.
C.
Given a Turing machine $M$ , decide if $M$ accepts all strings.
D.
Given a Turing machine $M$ , decide if $M$ takes more than 1073 steps on every string.

Question 5 · Theory of Computation · 2021_Set1 MCQ

For a Turing machine

M

⟨ M ⟩

denotes an encoding of

M

. Consider the following two languages.

L_{1} = {⟨ M ⟩ ∣ M takes more than 2021 steps on all inputs}

L_{2} = {⟨ M ⟩ ∣ M takes more than 2021 steps on some input}

Which one of the following options is correct?

A.
Both $L_{1}$ and $L_{2}$ are decidable.
B.
$L_{1}$ is decidable and $L_{2}$ is undecidable.
C.
$L_{1}$ is undecidable and $L_{2}$ is decidable.
D.
Both $L_{1}$ and $L_{2}$ are undecidable.

Question 6 · Theory of Computation · 2021_Set1 MSQ

Let $⟨ M ⟩$ denote an encoding of an automaton $M$ . Suppose that $Σ = {0, 1}$ . Which of the following languages is/are NOT recursive?

A.
$L = {⟨ M ⟩ ∣ M is a DFA such that L (M) = \emptyset}$
B.
$L = {⟨ M ⟩ ∣ M is a DFA such that L (M) = Σ^{*}}$
C.
$L = {⟨ M ⟩ ∣ M is a PDA such that L (M) = \emptyset}$
D.
$L = {⟨ M ⟩ ∣ M is a PDA such that L (M) = Σ^{*}}$

Try a question

Login to view the complete previous-year questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Turing Machines, Decidability and Undecidability PYQs for GATE CS

Perfect Shuffle and Sequence Permutations

Perfect Shuffle & Sequence Permutations

Intuition: The Two-Half Interleave

The Physical Analogy

Turing Machines, Decidability and Undecidability: Solved Questions with Step-by-Step Explanations (6 Problems)

More previous year questions (pyqs) in this unit