= 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$ with
$$
w\in A\quad\Longleftrightarrow\quad g(w)\mathbin\downarrow.
$$
For 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 is
$$
W_{h(w)}=
\begin{cases}
\mathbb W,&g(w)\mathbin\downarrow,\\
\varnothing,&g(w)\mathbin\uparrow.
\end{cases}
$$
In particular,
$$
w\in A
\quad\Longleftrightarrow\quad
h(w)\in W_{h(w)}
\quad\Longleftrightarrow\quad
h(w)\in\mathbf K.
$$
\b[Thus $h$ is a <many-one reduction> $A\leq_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>.]
Back to article page
