Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2017/ii/paper-3/11h/c/solution

Use uniform finite-stage enumerations and . Define a uniformly recursively enumerable set
The S-m-n theorem supplies a total computable index function with . If is finite of size , then , so is recursive. If is infinite, then for every a sufficiently late stage has both and , while no is ever enumerated. Hence , which is not recursive. Therefore . As usual the effective numbering indexes all programs; if malformed codes are included, send them to a fixed index of .

New to topics? Read the docs here!