Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 1 / 12I / v / Solution

First, $\mathbf{K}\in {\Sigma }_1$: the partial procedure on input $w$ simulates $f_{w,1}(w)$ and halts exactly when that computation halts.

For hardness, let $A\in {\Sigma }_1$. Choose a partial computable function $g$ withFor each fixed $w$, define a unary program $P_w$ as follows: on any input $x$, simulate $g(w)$; if that simulation halts, halt and output $x$, and otherwise run forever. The S-m-n theorem gives a total computable function $h$ that maps $w$ to a code for $P_w$. Its accepted language isIn particular,Thus $h$ is a many-one reduction $A{\le }_m\mathbf{K}$. Since $A$ was arbitrary, $\mathbf{K}$ is ${\Sigma }_1$-hard; together with membership this proves the many-one completeness of the halting problem.