PadhaikoAll subjects

Past exam question: 2082 Kartik (Back), Q5(b)(ii)

Theory of Computation · 2 marks

Open in the Padhaiko app

Topic: TM Variants, Unrestricted Grammar, Chomsky Hierarchy & Recursive Functions

Question

Show that the complement of recursive language is recursive.

Solution

Proof of Closure under Complementation for Recursive Languages: A language is recursive (decidable) if there exists a deterministic Turing Machine (a decider) that halts on every input such that:

We construct a new Turing Machine to decide the complement language :

  1. On input , simulates on .
  2. Since is a decider, it is guaranteed to halt in finite steps in either an accepting state or a rejecting state .
  3. If halts and accepts, halts and rejects.
  4. If halts and rejects, halts and accepts.

Formally, swaps the accept and reject halting states of : .

Because always halts, is guaranteed to halt on all inputs . Thus, decides , proving that the complement of every recursive language is recursive.

Answer:

Since a decider for recursive language halts on all inputs, swapping its accepting and rejecting outcomes creates decider that halts and accepts if and only if . Thus, recursive languages are closed under complementation.

All past exam questions for Theory of Computation