Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/ii/paper-1/12f/f/solution
Past exam of the mathematics course of the University of Cambridge 2025 ii Paper 1 12F f Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
For , map to a machine that initially enumerates nothing and, if the simulation establishing halts, enumerates every word. Its language is cofinite exactly when .
For , map to a machine that enumerates successively longer finite initial segments of while simulating . If the simulation never halts, every word is eventually enumerated; if it halts, enumeration stops with a finite language and therefore an infinite complement. Thus the constructed language is cofinite exactly when .
New to topics? Read the docs here!