[proofplan] Being $\Sigma_1$-complete for $\mathbb{K}$ means: $\mathbb{K} \in \Sigma_1$ and every $X \in \Sigma_1$ reduces to $\mathbb{K}$ under many-one reduction. The first half is immediate from [Halting Sets Are Computably Enumerable](/theorems/1822) and [Computably Enumerable Sets Are $\Sigma_1$](/theorems/1824). For the hardness half, an arbitrary $X \in \Sigma_1$ equals the domain of some computable partial function $f$ (via [Computably Enumerable Sets Are $\Sigma_1$](/theorems/1824)); we promote $f$ to a two-argument function $g(w, u) = f(w)$ that ignores $u$. Applying the $s$-$m$-$n$ theorem curries $g$ into a total computable $h$ such that $f_{h(w), 1}$ is the constant function $u \mapsto f(w)$. The domain $W_{h(w)}$ is then either $\mathbb{W}$ (if $f(w) \downarrow$) or $\varnothing$ (if $f(w) \uparrow$), which in particular decides whether $h(w) \in \mathbb{K}$ — giving the reduction $w \in X \iff h(w) \in \mathbb{K}$. [/proofplan] [step:Fix notation for register machines, the halting set, and the $\Sigma_1$-completeness target] Fix the course alphabet $\Sigma$ with distinguished accept letter $a \in \Sigma$ and write $\mathbb{W} = \Sigma^*$. The course fixes a computable coding of register machines $\operatorname{code} : \{\text{register machines}\} \to \mathbb{W}$ under which every word is the code of a machine; for $c \in \mathbb{W}$ and $k \ge 1$, write $f_{c, k} : \mathbb{W}^k \rightharpoonup \mathbb{W}$ for the arity-$k$ computable partial function computed by the machine with code $c$, and write $W_c := \operatorname{dom} f_{c, 1}$ for the associated arity-$1$ halting set. The *halting problem* is \begin{align*} \mathbb{K} &= \{w \in \mathbb{W} : f_{w, 1}(w) \downarrow\} = \{w \in \mathbb{W} : w \in W_w\}. \end{align*} A set $Z \subseteq \mathbb{W}$ is *$\Sigma_1$-complete* if (i) $Z \in \Sigma_1$ and (ii) for every $X \in \Sigma_1$, $X \leq_m Z$ (every $\Sigma_1$ set many-one-reduces to $Z$). The goal is to verify (i) and (ii) for $Z = \mathbb{K}$. We will use the $s$-$m$-$n$ theorem ([$s$-$m$-$n$ Theorem](/theorems/???)) in the form: for every computable partial function $g : \mathbb{W}^{k+1} \rightharpoonup \mathbb{W}$, there is a total computable $h : \mathbb{W} \to \mathbb{W}$ such that $f_{h(w), k}(u) = g(u, w)$ for all $w \in \mathbb{W}$ and $u \in \mathbb{W}^k$. (The course statement uses the convention $g(w, v)$ with $v$ the parameter; we apply it with the "parameter" being $w$.) [/step] [step:Show $\mathbb{K} \in \Sigma_1$] By [Halting Sets Are Computably Enumerable](/theorems/1822), $\mathbb{K}$ is computably enumerable. By [Computably Enumerable Sets Are $\Sigma_1$](/theorems/1824), every computably enumerable subset of $\mathbb{W}$ is $\Sigma_1$. Therefore $\mathbb{K} \in \Sigma_1$. [/step] [step:Reduce an arbitrary $X \in \Sigma_1$ to the domain of a computable partial function $f$] Let $X \in \Sigma_1$ be arbitrary. By [Computably Enumerable Sets Are $\Sigma_1$](/theorems/1824), $X$ is computably enumerable, so either $X = \varnothing$ or $X = \operatorname{dom} f$ for some computable partial function $f : \mathbb{W} \rightharpoonup \mathbb{W}$. *Empty case.* If $X = \varnothing$, pick any code $e \in \mathbb{W}$ with $W_e = \varnothing$ — for instance, the code of a register machine that enters an immediate infinite loop on every input. Then the constant function \begin{align*} h_{\varnothing} : \mathbb{W} &\to \mathbb{W}, \\ w &\mapsto e \end{align*} is total computable (L0 of Step 3 of the proof of [Recursive Implies Computable](/theorems/1817)), and for every $w \in \mathbb{W}$, $f_{h_\varnothing(w), 1}(h_\varnothing(w)) = f_{e, 1}(e) \uparrow$, so $h_\varnothing(w) \notin \mathbb{K}$. Thus $w \in \varnothing \iff h_\varnothing(w) \in \mathbb{K}$ (both sides are always false). This proves $\varnothing \leq_m \mathbb{K}$, handling the empty case. *Non-empty case.* From now on assume $X \neq \varnothing$, so $X = \operatorname{dom} f$ for some computable partial function $f : \mathbb{W} \rightharpoonup \mathbb{W}$. Fix such an $f$, witnessed by a register machine $M_f$ of arity $1$. [/step] [step:Promote $f$ to a two-argument function $g$ that ignores its second argument] Define \begin{align*} g : \mathbb{W}^2 &\rightharpoonup \mathbb{W}, \\ (u, w) &\mapsto f(w). \end{align*} [claim:$g$ is computable] A register machine $M_g$ of arity $2$ witnessing $g$ runs as follows. On input $(u, w)$ in registers $0, 1$: (a) Erase register $0$ (overwrite with $\varepsilon$), move the content of register $1$ into register $0$ (by the move primitive, total computable by L0 of Step 3 of the proof of [Recursive Implies Computable](/theorems/1817)). The result presents $w$ as the arity-$1$ input and erases the "ignored" argument $u$. (b) Run $M_f$ on register $0$. The computation diverges iff $f(w) \uparrow$, and otherwise halts with $f(w)$ in register $0$. Formally $g = f \circ \pi_2^2$ where $\pi_2^2 : \mathbb{W}^2 \to \mathbb{W}$, $(u, w) \mapsto w$ is the second projection (total computable by L0 of Step 3 of the proof of [Recursive Implies Computable](/theorems/1817)), and composition preserves computability of partial functions (L1 of the same step). Hence $g$ is computable. Its domain is $\operatorname{dom} g = \mathbb{W} \times \operatorname{dom} f = \mathbb{W} \times X$ (the ignored first coordinate contributes no constraint). [/claim] [/step] [step:Apply the $s$-$m$-$n$ theorem to curry $g$ in the second argument] Apply the $s$-$m$-$n$ theorem ([$s$-$m$-$n$ Theorem](/theorems/???)) to the computable partial function $g : \mathbb{W}^2 \rightharpoonup \mathbb{W}$, currying in the second argument (so $u$ is the remaining free input and $w$ is the parameter). We obtain a total computable function \begin{align*} h : \mathbb{W} &\to \mathbb{W} \end{align*} such that, for every $w \in \mathbb{W}$ and every $u \in \mathbb{W}$, \begin{align*} f_{h(w), 1}(u) &= g(u, w) = f(w). \end{align*} The meaning of the previous equation is: the arity-$1$ partial function computed by the machine with code $h(w)$ is the constant "$= f(w)$" function — independent of its input $u$, but inheriting convergence or divergence from $f(w)$. [/step] [step:Compute the halting set $W_{h(w)}$ by case distinction on $f(w)$] [claim:For every $w \in \mathbb{W}$, $W_{h(w)} = \mathbb{W}$ if $w \in X$ and $W_{h(w)} = \varnothing$ if $w \notin X$] Fix $w \in \mathbb{W}$. By Step 5, $f_{h(w), 1}(u) = f(w)$ for every $u \in \mathbb{W}$ — meaning both sides converge together or diverge together, and if they converge they take the same value. *Case $w \in X$.* Then $f(w) \downarrow$ (by $X = \operatorname{dom} f$), so $f_{h(w), 1}(u) = f(w)$ converges for every $u$. Hence every $u \in \mathbb{W}$ lies in $\operatorname{dom} f_{h(w), 1} = W_{h(w)}$, i.e. $W_{h(w)} = \mathbb{W}$. *Case $w \notin X$.* Then $f(w) \uparrow$, so $f_{h(w), 1}(u) = f(w)$ diverges for every $u$. Hence no $u \in \mathbb{W}$ lies in $W_{h(w)}$, i.e. $W_{h(w)} = \varnothing$. [/claim] [/step] [step:Derive the reduction $X \leq_m \mathbb{K}$ via $h$] We show $h$ is a many-one reduction from $X$ to $\mathbb{K}$: it is total computable (Step 5), and for every $w \in \mathbb{W}$, \begin{align*} w \in X &\iff h(w) \in \mathbb{K}. \end{align*} $(\Rightarrow)$ If $w \in X$, then by Step 6, $W_{h(w)} = \mathbb{W}$, so in particular $h(w) \in W_{h(w)}$, i.e. $f_{h(w), 1}(h(w)) \downarrow$. By the definition of $\mathbb{K}$ (Step 1), $h(w) \in \mathbb{K}$. $(\Leftarrow)$ Contrapositively, suppose $w \notin X$. Then by Step 6, $W_{h(w)} = \varnothing$, so $h(w) \notin W_{h(w)}$, i.e. $f_{h(w), 1}(h(w)) \uparrow$. Hence $h(w) \notin \mathbb{K}$. Combining, $X \leq_m \mathbb{K}$. [guided] We unpack why this reduction works and why we had to "waste an argument" in $g$. *The target: self-applying convergence.* The set $\mathbb{K}$ is defined by the self-application predicate "$f_{w, 1}(w) \downarrow$" — the machine coded by $w$ halts on input $w$. Deciding membership in $\mathbb{K}$ therefore requires producing, from an arbitrary input $w$, a *code* whose self-application is equivalent to $w \in X$. *Why not try $h(w) = \operatorname{code}(M_f)$?* This candidate is constant in $w$, so it cannot distinguish $w \in X$ from $w \notin X$. We need $h$ to depend on $w$. *The $s$-$m$-$n$ idea.* The $s$-$m$-$n$ theorem is the mechanism by which "dependence on a parameter" becomes computable: it says that plugging a parameter into a multi-argument computable function yields a *code* that depends computably on the parameter. Formally, for any computable $g : \mathbb{W}^{k+1} \rightharpoonup \mathbb{W}$, the partial application $(u_1, \ldots, u_k) \mapsto g(u_1, \ldots, u_k, w)$ is itself computable (fix $w$, run $g$), but what matters is that its *code* can be computed totally from $w$. That is the promotion from "sliced semantics" to "computable code selection". *Why make $g$ ignore its first argument?* We want the resulting sliced function $u \mapsto g(u, w) = f(w)$ to be *constant* in $u$, because then $W_{h(w)} = \{u : f_{h(w), 1}(u) \downarrow\}$ is all-or-nothing: either $f(w)$ converges and $W_{h(w)} = \mathbb{W}$, or $f(w)$ diverges and $W_{h(w)} = \varnothing$. The all-or-nothing is what lets us decide $h(w) \in \mathbb{K}$ by simply asking "is $W_{h(w)} \neq \varnothing$?" — equivalently, "is $f(w)$ defined?" — which is exactly "$w \in X$". *Why is the self-application $f_{h(w), 1}(h(w))$ the right thing to check?* Because of the all-or-nothing structure. When $W_{h(w)} = \mathbb{W}$, *every* input converges — in particular $h(w)$ itself. When $W_{h(w)} = \varnothing$, *no* input converges — in particular $h(w)$. The self-application is just one of many equivalent ways to witness definedness; we use it because that is how $\mathbb{K}$ is defined. *Where did we use totality of $h$?* A reduction must be total — see the definition of $\leq_m$ (Step 1 of the proof of [Many-One Reducibility Is a Preorder](/theorems/???)). The $s$-$m$-$n$ theorem gives this: $h$ is *total* computable, not merely partial. Even when $f(w) \uparrow$, the code $h(w)$ is produced — it is the code of a machine that loops on all inputs. *Summary of dependencies.* Step 2 depends on [Halting Sets Are Computably Enumerable](/theorems/1822) and [Computably Enumerable Sets Are $\Sigma_1$](/theorems/1824). Step 3 depends on [Computably Enumerable Sets Are $\Sigma_1$](/theorems/1824). Step 5 depends on the [$s$-$m$-$n$ Theorem](/theorems/???). Step 7 depends only on the definition of $\mathbb{K}$ and the case analysis of Step 6. [/guided] [/step] [step:Conclude] Step 2 establishes $\mathbb{K} \in \Sigma_1$. Steps 3–7 establish that for every $X \in \Sigma_1$, $X \leq_m \mathbb{K}$: the empty case is handled by a constant reduction to a non-halting code; the non-empty case curries the witnessing $f$ via $s$-$m$-$n$ to produce a total computable $h$ with $W_{h(w)} \in \{\varnothing, \mathbb{W}\}$ that cleanly tracks $w \in X$. Hence $\mathbb{K}$ is $\Sigma_1$-complete. [/step]