Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 3 / 11H (Automata and formal languages)

A many-one reduction $A{\le }_{m}B$ is a total computable function $f:\mathbb{N}\to \mathbb{N}$ with $x\in A⟺f(x)\in B$. If $B$ is recursively enumerable, compute $f(x)$ and run a semidecision procedure for $B$ on that value. It halts exactly when $x\in A$, so $A$ is recursively enumerable. Totality of $f$ is essential to this argument.

The S-m-n theorem says that parameters can be compiled effectively into program indices: for a standard effective numbering, there is a total computable function $s_m^n$ with ${\phi }_{s_m^n(e,\mathbf{a})}(\mathbf{x})={\phi }_e(\mathbf{a},\mathbf{x})$ for partial computable functions of $m+n$ arguments.

Write $K=\{e:{\phi }_e(e)\text{ halts}\}$, a recursively enumerable halting problem. If $X$ is recursively enumerable, make a program with parameter $x$ which ignores its input and runs a semidecision procedure for $x\in X$, halting when that procedure halts. By the S-m-n theorem its index $f(x)$ is total computable and $f(x)\in K⟺x\in X$. Conversely, $X{\le }_{m}K$ implies that $X$ is recursively enumerable by the previous construction. Thus $\boxed{X\text{ is r.e.}⟺X{\le }_{m}K}$.

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$.