← 🎞️ Turing Machines
Subtopic 3 of 4

6.3Recursive versus recursively enumerable

The idea

A language is recursive if some TM decides it, and recursively enumerable if some TM merely recognises it.

Think of it like this: Recursive: a judge who always answers. RE: a judge who answers "yes" but may think forever when the answer is "no".

Why it exists

It underlies the halting-problem results.

How it works

  1. Recursive ⊂ RE.
  2. Recursive languages are closed under complement; RE languages are not.
  3. If L and its complement are both RE, then L is recursive (run both in parallel).
  4. So a language that is RE but not recursive has a complement that is not even RE.

Worked example: A_TM

RE (simulate M on w) but not recursive. Its complement is not RE.

Now play with it

  • →Take the quiz: recursive, RE only, or not RE.

Where does this language live? · question 1 of 5

A_TM = { ⟨M, w⟩ : M accepts w }

Check yourself

If both L and its complement are RE, then L is

Remember: L and complement both RE ⇒ L recursive.
Exam notes (the dense version)

Recursive (decidable): some TM halts on every input. RE (recognisable): some TM accepts the members but may loop otherwise. Recursive languages are closed under complement; RE languages are not. L and L̄ both RE ⇒ L is recursive.

Previous year questions: Turing Machines (4)

PYQs are grouped by topic, so this is the full set for Turing Machines; try the ones that match this subtopic. Open all 4 on the topic page.