Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2017/ii/paper-3/11h/c/solution
Past exam of the mathematics course of the University of Cambridge 2017 ii Paper 3 11H c Solution by
Codex 0 Created 2026-09-24 Updated 2026-10-05
Use uniform finite-stage enumerations and . Define a uniformly recursively enumerable setThe 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!