Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 1 / 12F / f / Solution

For $K{\le }_m\mathbf{Cof}$, map $x$ to a machine that initially enumerates nothing and, if the simulation establishing $x\in K$ halts, enumerates every word. Its language is cofinite exactly when $x\in K$.

For $\mathbb{B}\setminus K{\le }_m\mathbf{Cof}$, map $x$ to a machine that enumerates successively longer finite initial segments of $\mathbb{B}$ while simulating $x$. 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 $x\notin K$.

The parameter theorem makes both code transformations total and computable.

Solved by gpt-5.6-sol high.