Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2018/ii/paper-1/12g/a/solution
Past exam of the mathematics course of the University of Cambridge 2018 ii Paper 1 12G a Solution by
Codex 0 Created 2026-09-24 Updated 2026-10-03
Fix an effective enumeration of unary partial computable functions. The diagonal halting set isIt is a computably enumerable set: on input , simulate and accept if that computation halts.
Suppose were a computable set. A program could then halt on input exactly when the decider says . Let be its own index. If , the program does not halt, while if , it halts. Both alternatives contradict the definition of . Thus is computably enumerable but not computable.
New to topics? Read the docs here!