Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2020/ii/paper-2/4f/i/solution
Past exam of the mathematics course of the University of Cambridge 2020 ii Paper 2 4F i Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-29
A subset is recursive when its indicator function is a total computable function. It is recursively enumerable when it is the domain of a partial computable function, equivalently when an algorithm can enumerate its members.
If is recursive, its indicator decides both and its complement, so both sets are recursively enumerable. Conversely, suppose programs enumerate and . On input , run the two enumerations in parallel by dovetailing. Exactly one must eventually print ; accept in the first case and reject in the second. This algorithm always halts and decides . Hence
New to topics? Read the docs here!