🎞️ Turing Machines
Why it matters: Recursive versus recursively enumerable, TM variants, and what a TM can do.
Subtopics
Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 4 done.
1The Turing machine model
2Variants and equivalent models
3Recursive versus recursively enumerable
4Church–Turing thesis and TM design
Formulas
TM definition
(Q, Σ, Γ, δ, q₀, B, F), δ: Q × Γ → Q × Γ × {L, R}
Recursive ⊂ RE
every recursive language is RE; not conversely
Complement rule
L, L̄ both RE ⇔ L recursive
Simulation cost
multi-tape TM → single-tape: O(t²); NTM → DTM: exponential
What GATE asks from this
Question types seen repeatedly in past papers. More stars means more frequent.
★★★
Recursive / RE / neither for a described language
Use closure rules and the "L and complement both RE" fact.
★★★
Equivalence of TM variants
Which TM variants add no power.
★★★
What does this TM compute / accept
Trace a small TM (e.g. aⁿbⁿ marker algorithm).
Ratings are approximate, based on recurring patterns in past GATE CSE papers.
Previous year questions
4 real questions from the official GATE CSE papers (2013 to 2018), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.
4 questions · 0 correct of 0 attempted · marks 0 / 6
Year:
GATE 2018 · Q7MCQ1 mark
The set of all recursively enumerable languages is
GATE 2017 Set 1 · Q39MCQ2 marks
Let A and B be finite alphabets and let # be a symbol outside both A and B. Let f be a total function from A* to B*. We say f is computable if there exists a Turing machine M which given an input x in A*, always halts with f(x) on its tape. Let Lf denote the language { x # f(x) | x ∈ A* }. Which of the following statements is true:
GATE 2014 Set 1 · Q35MCQ2 marks
Let L be a language and its complement be denoted L'. Which one of the following is NOT a viable possibility?
GATE 2013 Code A · Q17MCQ1 mark
Which of the following statements is/are FALSE?
1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
2. Turing recognizable languages are closed under union and complementation.
3. Turing decidable languages are closed under intersection and complementation.
4. Turing recognizable languages are closed under union and intersection.
1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
2. Turing recognizable languages are closed under union and complementation.
3. Turing decidable languages are closed under intersection and complementation.
4. Turing recognizable languages are closed under union and intersection.
Common traps
A TM that loops on some input is a recogniser, not a decider.
Nondeterminism adds no computability power to TMs (unlike speed).
The class of RE languages is closed under union and intersection, not complement.