= Solution
Use uniform finite-stage enumerations $W_{n,s}$ and $K_s$. Define a uniformly <recursively enumerable> <set>
$$
V_n=\{x:\exists s\ (x\in K_s\text{ and }x<|W_{n,s}|)\}.
$$
The <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,\ldots,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\iff f(n)\in Q,\quad P\leq_mQ}$. As usual the effective numbering indexes all programs; if malformed codes are included, send them to a fixed index of $K$.
Back to article page
