Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2020/ii/paper-2/4f/i/solution

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!