Recall warm-up
- Is a nondeterministic TM more powerful than a deterministic one?
Stuck? Peek at 4.2 TM variants, linear bounded automata and context-sensitive languages
- Multi-tape (O(t²)), nondeterministic (BFS, exponential), two-way tape, 2-stack PDA, 2 counters: all = TM.
- LBA: nondeterministic TM within the input ⇔ CSG (|α| ≤ |β|) ⇔ CSL.
- CFL ⊊ CSL (aⁿbⁿcⁿ). Every CSL is decided by an always-halting TM.
- What are the three outcomes of a TM run?
Stuck? Peek at 4.1.1 The Turing machine: tape, head, states, halting
- TM (Q, Σ, Γ, δ, q₀, □, F), δ : Q × Γ → Q × Γ × {L,R} (partial).
- ID α q β (head on first of β). Outcomes: accept, reject (or stuck), loop.
- Tape: read/write anywhere, unbounded. L(M) = accepted strings.
- Do all standard questions about regular languages have always-terminating algorithms?
Stuck? Peek at 2.4.2 Algorithms for regular languages
- Membership: run. Emptiness: reachable F? Finiteness: trim + cycle (or lengths n..2n−1). Universality: complement + emptiness. Equivalence: minimize & compare, or symmetric difference empty. Containment: L₁ ∩ L̅₂ = ∅.
- All these have always-terminating algorithms for regular languages.
The Hook
Two programs both answer “is this input in L?”. Program A always finishes. Program B finishes with “yes” on every yes-input, but on some no-inputs it runs forever. In practice A is a tool you can trust; B is a search that may never end. TOC gives them names, and the gap between them is the subject of Phase 5.
Predict First
Program B never prints a wrong answer. Why is it still less useful than A?
Core Concept
Prediction check
Because when B has been running for an hour, you can’t tell whether the answer is “no” or “not yet”. A always gives a verdict.
Recognizers and RE languages
Deciders and recursive languages
“Decidable problem” = its language is recursive. Every recursive language is RE (a decider is a recognizer).
Why the name “enumerable”
L is RE iff some TM (an enumerator) can print a list containing exactly the strings of L, in some order, possibly forever. Recognizer → enumerator: run the recognizer on all strings in a dovetailed way (step 1 on string 1; steps 1–2 on strings 1–2; …) and print a string when it is accepted. Enumerator → recognizer: wait for w to appear in the list.
L is recursive iff it can be enumerated in shortlex order (0.3.2).
| round | run string 1 | run string 2 | run string 3 | … |
|---|---|---|---|---|
| 1 | 1 step | |||
| 2 | 2 steps | 2 steps | ||
| 3 | 3 steps | 3 steps | 3 steps | |
| … | … | … | … | … |
Terminology map
GATE uses all of these interchangeably:
| decider side | recognizer side |
|---|---|
| recursive | recursively enumerable (RE) |
| decidable | semi-decidable / partially decidable |
| Turing-decidable | Turing-recognizable / Turing-acceptable |
| total TM (always halts) | any TM |
Putting it together
- Deciders always halt; recognizers may loop on non-members.
- Recursive = decidable; RE = recognizable = enumerable.
- Every recursive language is RE.
Visual
input w
│
┌──────▼───────┐ decider: always reaches ACCEPT or REJECT
│ M │
└──┬───┬───┬───┘ recognizer: ACCEPT on w ∈ L; on w ∉ L maybe REJECT, maybe ∞
ACC REJ ∞ (loops)Worked Examples
Is every regular language recursive?
Show the full solution
Yes — a DFA always halts, and a TM can simulate it.
Is every CFL recursive?
Show the full solution
Yes: the CYK algorithm always halts. (Even every CSL is recursive.)
M accepts every string in L and loops on every string not in L. Which are true? (i) L is RE. (ii) L is recursive. (iii) M is a decider. (iv) L could still be recursive via another machine.
Show the full solution
(i) true. (ii) not necessarily. (iii) false. (iv) true — one machine looping does not stop another machine from deciding L. Answer: (i) and (iv).
GATE Traps
- A language is recursive if SOME TM decides it; one looping TM proves nothing.
- “Decidable” = recursive; “semi-decidable / recognizable” = RE.
- REC ⊆ RE always.
- Rejecting and looping are both “not accepting”; only deciders guarantee rejection.
Memory Hook
Decider = a judge who always rules. Recognizer = a detective who announces when guilt is proven, but on the innocent may search forever.
Connect the Dots
Now place every class you know on one ladder: Regular ⊂ DCFL ⊂ CFL ⊂ CSL ⊂ REC ⊂ RE — the Chomsky hierarchy.
Self-Test
- MCQ
L is recursive iff:
- some TM accepts L
- some TM accepts L and halts on every input
- every TM for L halts
- L is finite
- MSQ
Which mean the same as “recursively enumerable”?
- Turing-recognizable
- semi-decidable
- decidable
- listable by an enumerator
- MCQ
Every CFL is:
- RE but maybe not recursive
- recursive
- regular
- not RE
- MCQ
Why is dovetailing needed to enumerate an RE language?
- to sort strings
- so a looping run on one string doesn’t block the others
- to save tape
- to make the TM deterministic
Rule Card
- Recognizer: accepts L, may loop outside. RE = recognizable = semi-decidable = enumerable.
- Decider: halts always. Recursive = decidable.
- REC ⊆ RE. Enumerator ⇔ recognizer (dovetailing). Shortlex enumeration ⇔ recursive.
Concept Ledger
- recognizer
- recursively enumerable (RE) / semi-decidable
- decider (total TM)
- recursive / decidable
- enumerator
- dovetailing
Answer Vault
Reveal answers when you’re ready
Warm-up answers
- No.
- Accept, reject, loop.
- Yes.
Self-test answers
- B — A decider exists.
- A: That is RE.
- C: Too strong.
- D: No.
- ABD — All are RE.
- C: That is recursive.
- B — CYK decides it.
- A: It is recursive.
- C: No.
- D: No.
- B — Interleave runs.
- A: Not the purpose.
- C: No.
- D: No.
Flashcards
- Recursive vs RE?
Reveal answer
Recursive: some TM halts on all inputs and accepts L. RE: some TM accepts exactly L (may loop outside). - Other names for RE?
Reveal answer
Turing-recognizable, semi-decidable, enumerable. - Is every CFL recursive?
Reveal answer
Yes.