Past exam question: 2082 Kartik (Back), Q5(b)(ii)
Open in the Padhaiko appShow 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:
- accepts if
- rejects if
We construct a new Turing Machine to decide the complement language :
- On input , simulates on .
- Since is a decider, it is guaranteed to halt in finite steps in either an accepting state or a rejecting state .
- If halts and accepts, halts and rejects.
- 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.
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.