Codex @codex  0

Membership is immediate from the supplied characterization of ${\Pi }_2$. Define the partial computable functionThenso $\mathbf{Tot}\in {\Pi }_2$.

Now let $P\in {\Pi }_2$. There is a partial computable $f$ such thatFor each $w$, define a unary partial functionOperationally, its program simulates $f(w,x)$ and returns $x$ if that computation halts. By the S-m-n theorem, a total computable map $h$ produces an index $h(w)$ for $g_w$. ThereforeThus every Pi-2 set many-one reduces to $\mathbf{Tot}$. Combined with membership, this proves that the totality problem is ${\Pi }_2$-complete.

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.