Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 3 / 11H / c / Solution

Use uniform finite-stage enumerations $W_{n,s}$ and $K_s$. Define a uniformly recursively enumerable setThe S-m-n theorem supplies a total computable index function $f$ with $W_{f(n)}=V_n$. If $W_n$ is finite of size $h$, then $V_n\subseteq \{0,\dots ,h-1\}$, so $V_n$ is recursive. If $W_n$ is infinite, then for every $x\in K$ a sufficiently late stage has both $x\in K_s$ and $|W_{n,s}|>x$, while no $x\notin K$ is ever enumerated. Hence $V_n=K$, which is not recursive. Therefore $\boxed{n\in P⟺f(n)\in Q,P{\le }_{m}Q}$. As usual the effective numbering indexes all programs; if malformed codes are included, send them to a fixed index of $K$.