[proofplan] Let $I \subseteq \mathbb{W}$ be a non-trivial index set: it is closed under weak equivalence ($W_v = W_u \Rightarrow (v \in I \iff u \in I)$), and both $I \neq \varnothing$ and $I \neq \mathbb{W}$. Fix a code $e$ of a perpetually-looping machine, so $W_e = \varnothing$. By non-triviality, $I$ and its complement are both non-empty; by index-set closure, either $e \in I$ (in which case non-triviality picks a "positive" witness $w \notin I$ with $W_w \neq \varnothing$) or $e \notin I$ (in which case non-triviality picks a "positive" witness $w \in I$ with $W_w \neq \varnothing$). In both cases, the same $s$-$m$-$n$ construction of [$\mathbb{K}$ Is $\Sigma_1$-Complete](/theorems/1834) — applied to the computable partial function $g(u, v) = f_{w, 1}(v)$ that ignores its first input $u$ and runs the $w$-machine on the second input $v$ — produces a total computable $h$ with $W_{h(u)} = W_w$ when $u \in \mathbb{K}$ and $W_{h(u)} = \varnothing$ when $u \notin \mathbb{K}$. Index-set closure then converts "$W_{h(u)} \in \{W_w, \varnothing\}$" into "$h(u) \in \{w, e\}$ up to $\sim$", so $h$ reduces $\mathbb{W} \setminus \mathbb{K}$ or $\mathbb{K}$ to $I$ according to the case. In both cases the source set ($\mathbb{W} \setminus \mathbb{K}$ or $\mathbb{K}$) is non-computable (by [The Halting Problem](/theorems/1823) and closure of computable sets under complement, [Computable Sets Are $\Delta_1$](/theorems/1825)), so $I$ cannot be computable either — computable sets being $\leq_m$-downward-closed. [/proofplan] [step:Fix notation, weak equivalence, and the empty-domain witness $e$] 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 so that every word $c \in \mathbb{W}$ is a code; for arity $k = 1$, write $f_{c, 1} : \mathbb{W} \rightharpoonup \mathbb{W}$ for the arity-$1$ computable partial function computed by the machine with code $c$, and $W_c := \operatorname{dom} f_{c, 1}$. *Weak equivalence.* For $v, u \in \mathbb{W}$, write $v \sim u$ iff $W_v = W_u$; this is an equivalence relation on $\mathbb{W}$. *Index sets.* A set $I \subseteq \mathbb{W}$ is an *index set* iff it is closed under $\sim$: if $v \in I$ and $v \sim u$ then $u \in I$. Equivalently, $I$ is a union of $\sim$-equivalence classes. The *trivial index sets* are $\varnothing$ and $\mathbb{W}$; $I$ is *non-trivial* iff $I \neq \varnothing$ and $I \neq \mathbb{W}$. *The halting problem.* $\mathbb{K} = \{w \in \mathbb{W} : f_{w, 1}(w) \downarrow\} = \{w \in \mathbb{W} : w \in W_w\}$. *The empty-domain witness.* Fix once and for all a code $e \in \mathbb{W}$ of a register machine that enters an immediate infinite loop on every input, so \begin{align*} W_e &= \varnothing. \end{align*} Such a machine exists (one line of register-machine code suffices: jump to itself), and the coding assigns it a code $e$. [/step] [step:Fix a non-trivial index set $I$ and split on whether $e \in I$] Let $I \subseteq \mathbb{W}$ be a non-trivial index set. Since $I$ is non-trivial, $e \in I$ or $e \notin I$; we handle the two cases separately in Steps 4 and 5. They share a single $s$-$m$-$n$ construction, which we now carry out once. [/step] [step:Build the $s$-$m$-$n$-produced reduction $h$ from a "positive" witness $w$] Suppose we are given $w \in \mathbb{W}$ with $W_w \neq \varnothing$ (the role of $w$ will be pinned down in Steps 4 and 5). Fix a register machine $M_w$ of arity $1$ with code $w$, so $f_{w, 1}$ is the partial function it computes. Define \begin{align*} g : \mathbb{W}^2 &\rightharpoonup \mathbb{W}, \\ (v, u) &\mapsto f_{w, 1}(v). \end{align*} [claim:$g$ is computable] $g$ ignores its second argument and returns the result of running $M_w$ on its first. Explicitly, $g = f_{w, 1} \circ \pi_1^2$, where $\pi_1^2 : \mathbb{W}^2 \to \mathbb{W}$, $(v, u) \mapsto v$ is the first projection (total computable by L0 of Step 3 of the proof of [Recursive Implies Computable](/theorems/1817)). By L1 of the same step, $g$ is computable. [/claim] Apply the [$s$-$m$-$n$ Theorem](/theorems/???) to $g$, treating $u$ as the parameter: we obtain a total computable \begin{align*} h : \mathbb{W} &\to \mathbb{W} \end{align*} such that for every $u \in \mathbb{W}$ and $v \in \mathbb{W}$, \begin{align*} f_{h(u), 1}(v) &= g(v, u) = f_{w, 1}(v). \end{align*} *Wait* — this says $f_{h(u), 1} = f_{w, 1}$ for every $u$, which would make $W_{h(u)} = W_w$ unconditionally, not depending on whether $u \in \mathbb{K}$. That is not what the strategy needs. The fix: we must *force* divergence of $f_{h(u), 1}$ when $u \notin \mathbb{K}$. We do this by gating $g$ on the halting of $f_{u, 1}(u)$. Replace $g$ above by the *gated* version \begin{align*} \tilde g : \mathbb{W}^2 &\rightharpoonup \mathbb{W}, \\ (v, u) &\mapsto \begin{cases} f_{w, 1}(v) & \text{if } f_{u, 1}(u) \downarrow, \\ \uparrow & \text{if } f_{u, 1}(u) \uparrow. \end{cases} \end{align*} [claim:$\tilde g$ is computable] A register machine $M_{\tilde g}$ witnessing $\tilde g$ runs on input $(v, u)$ as follows: (a) Save a master copy of $v$ in a scratch register. (b) Run the *universal* register machine on input $(u, u)$ — equivalently, simulate $M_u$ on input $u$. Computability of this subroutine is the content of the universal machine construction (Step 2 of the proof of [Halting Sets Are Computably Enumerable](/theorems/1822), or [Computability of the Configuration Function](/theorems/1818) combined with minimisation). If $f_{u, 1}(u) \uparrow$, the subroutine diverges and so does $M_{\tilde g}$; if $f_{u, 1}(u) \downarrow$, control passes to (c) with the master copy of $v$ recoverable from the scratch register. (c) Restore $v$ from the scratch register into input register $0$ and run $M_w$ on $v$. The outcome is $f_{w, 1}(v)$. Formally, $\tilde g = g \circ ((\pi_1^2, (\mathrm{univ}_1 \circ \Delta_2) \circ \pi_2^2))$ or any equivalent composition: we use $f_{u, 1}(u)$ as a convergence gate, then compute $g(v, u) = f_{w, 1}(v)$. By L1 of Step 4 of the proof of [Recursive Implies Computable](/theorems/1817), the composition of computable partial functions is computable; hence $\tilde g$ is computable. [/claim] Apply the [$s$-$m$-$n$ Theorem](/theorems/???) to $\tilde g$, treating $u$ as the parameter: we obtain a total computable \begin{align*} h : \mathbb{W} &\to \mathbb{W} \end{align*} such that for every $u \in \mathbb{W}$ and $v \in \mathbb{W}$, \begin{align*} f_{h(u), 1}(v) &= \tilde g(v, u) = \begin{cases} f_{w, 1}(v) & \text{if } u \in \mathbb{K}, \\ \uparrow & \text{if } u \notin \mathbb{K}. \end{cases} \end{align*} [claim:For every $u \in \mathbb{W}$: $W_{h(u)} = W_w$ if $u \in \mathbb{K}$, and $W_{h(u)} = \varnothing$ if $u \notin \mathbb{K}$] Fix $u \in \mathbb{W}$. *Case $u \in \mathbb{K}$.* Then $f_{u, 1}(u) \downarrow$, so by the previous display $f_{h(u), 1}(v) = f_{w, 1}(v)$ for every $v$ (in particular, both sides converge together and agree when they do). Hence \begin{align*} W_{h(u)} &= \operatorname{dom} f_{h(u), 1} = \operatorname{dom} f_{w, 1} = W_w. \end{align*} *Case $u \notin \mathbb{K}$.* Then $f_{u, 1}(u) \uparrow$, so $f_{h(u), 1}(v) \uparrow$ for every $v$, giving $W_{h(u)} = \varnothing$. [/claim] Translating via weak equivalence: $u \in \mathbb{K} \Rightarrow h(u) \sim w$ and $u \notin \mathbb{K} \Rightarrow h(u) \sim e$. This is the technical core used in both cases of the theorem. [guided] We explain the double-slot $s$-$m$-$n$ construction. *Why two arguments?* The $s$-$m$-$n$ theorem demands a multi-argument function, and we want the output *code* $h(u)$ to depend on $u$. So $u$ is the parameter, and we need at least one other argument (here $v$) to be curried out. *Why gate by $f_{u, 1}(u)$?* Because we need $W_{h(u)}$ to distinguish $u \in \mathbb{K}$ from $u \notin \mathbb{K}$. Without the gate, $W_{h(u)} = W_w$ unconditionally — the output code would be indistinguishable across values of $u$. By inserting the gate "run the $u$-machine on $u$ first and only then run the $w$-machine on $v$", we arrange that $W_{h(u)}$ is empty precisely when $u \notin \mathbb{K}$. *Why is the gate computable?* Because running $f_{u, 1}(u)$ — the universal simulator applied to input $(u, u)$ — is a computable partial function. It halts exactly when $u \in \mathbb{K}$. We do not need to *decide* $u \in \mathbb{K}$ (which would contradict [The Halting Problem](/theorems/1823)); we only need to *implement the gate* as a partial computation, which is fine because partial computations are exactly what code-producing constructions allow. *Why are the two cases $u \in \mathbb{K}$, $u \notin \mathbb{K}$ all-or-nothing for $W_{h(u)}$?* The gate is on $u$ alone, not on $v$; it blocks or admits the entire $v$-computation uniformly. So for fixed $u$, the function $v \mapsto f_{h(u), 1}(v)$ is either identically $f_{w, 1}$ or identically undefined. *The role of weak equivalence.* Since $I$ is an index set, membership in $I$ depends only on $W_v$, not on $v$ itself. The identity $W_{h(u)} = W_w$ (for $u \in \mathbb{K}$) thus forces $h(u) \in I \iff w \in I$, and similarly $W_{h(u)} = W_e = \varnothing$ (for $u \notin \mathbb{K}$) forces $h(u) \in I \iff e \in I$. This pattern — "translate a domain equality into an $I$-membership equality via index-set closure" — is the signature move of Rice-style arguments. *Comparison with [$\mathbb{K}$ Is $\Sigma_1$-Complete](/theorems/1834).* The construction there was simpler: $g(u, w) = f(w)$ ignored *both* a real halting test and its first argument, producing $W_{h(w)} \in \{\mathbb{W}, \varnothing\}$ by direct convergence inheritance from $f(w)$. Here we need to *insert* a halting test on $u$ itself, because the input $u$ ranges over $\mathbb{W}$ (testing membership in $\mathbb{K}$), not over $X = \operatorname{dom} f$. The gating pattern replaces "convergence of $f(w)$" by "convergence of $f_{u, 1}(u)$". [/guided] [/step] [step:Case 1 — $e \in I$: reduce $\mathbb{W} \setminus \mathbb{K}$ to $I$] Suppose $e \in I$. Since $I$ is non-trivial, $I \neq \mathbb{W}$, so there exists $w \notin I$. *Verify $W_w \neq \varnothing$.* If $W_w = \varnothing$, then $w \sim e$; since $e \in I$ and $I$ is an index set, $w \in I$, contradicting $w \notin I$. Hence $W_w \neq \varnothing$. Apply Step 3 with this $w$. We obtain a total computable $h : \mathbb{W} \to \mathbb{W}$ with $h(u) \sim w$ if $u \in \mathbb{K}$ and $h(u) \sim e$ if $u \notin \mathbb{K}$. [claim:$h$ is a many-one reduction from $\mathbb{W} \setminus \mathbb{K}$ to $I$] We check: for every $u \in \mathbb{W}$, $u \in \mathbb{W} \setminus \mathbb{K} \iff h(u) \in I$. *Case $u \in \mathbb{K}$.* Then $h(u) \sim w$, and $I$ is an index set, so $h(u) \in I \iff w \in I$. Since $w \notin I$, $h(u) \notin I$. Also $u \in \mathbb{K}$, so $u \notin \mathbb{W} \setminus \mathbb{K}$. Both sides are false. *Case $u \notin \mathbb{K}$.* Then $h(u) \sim e$, and $I$ is an index set, so $h(u) \in I \iff e \in I$. Since $e \in I$, $h(u) \in I$. Also $u \notin \mathbb{K}$, so $u \in \mathbb{W} \setminus \mathbb{K}$. Both sides are true. Combining, $\mathbb{W} \setminus \mathbb{K} \leq_m I$. [/claim] By [The Halting Problem](/theorems/1823), $\mathbb{K}$ is not computable. By closure of computable sets under complement (Step 2 of the proof of [Closure Properties of Computable Sets](/theorems/1828)), if $\mathbb{W} \setminus \mathbb{K}$ were computable then so would be $\mathbb{K}$; hence $\mathbb{W} \setminus \mathbb{K}$ is not computable. Now if $I$ were computable, then $\mathbb{W} \setminus \mathbb{K} \leq_m I$ together with [Computable Sets Are Downward-Closed Under $\leq_m$](/theorems/???) (i.e. $A \leq_m B$ and $B$ computable $\Rightarrow$ $A$ computable) would force $\mathbb{W} \setminus \mathbb{K}$ to be computable — a contradiction. Hence $I$ is not computable. [/step] [step:Case 2 — $e \notin I$: reduce $\mathbb{K}$ to $I$] Suppose $e \notin I$. Since $I$ is non-trivial, $I \neq \varnothing$, so there exists $w \in I$. *Verify $W_w \neq \varnothing$.* If $W_w = \varnothing$, then $w \sim e$; since $e \notin I$ and $I$ is an index set, $w \notin I$, contradicting $w \in I$. Hence $W_w \neq \varnothing$. Apply Step 3 with this $w$. We obtain a total computable $h : \mathbb{W} \to \mathbb{W}$ with $h(u) \sim w$ if $u \in \mathbb{K}$ and $h(u) \sim e$ if $u \notin \mathbb{K}$. [claim:$h$ is a many-one reduction from $\mathbb{K}$ to $I$] We check: for every $u \in \mathbb{W}$, $u \in \mathbb{K} \iff h(u) \in I$. *Case $u \in \mathbb{K}$.* Then $h(u) \sim w$, so $h(u) \in I \iff w \in I$. Since $w \in I$, $h(u) \in I$. Both sides are true. *Case $u \notin \mathbb{K}$.* Then $h(u) \sim e$, so $h(u) \in I \iff e \in I$. Since $e \notin I$, $h(u) \notin I$. Both sides are false. Combining, $\mathbb{K} \leq_m I$. [/claim] By [The Halting Problem](/theorems/1823), $\mathbb{K}$ is not computable. If $I$ were computable, then $\mathbb{K} \leq_m I$ together with [Computable Sets Are Downward-Closed Under $\leq_m$](/theorems/???) would force $\mathbb{K}$ to be computable — a contradiction. Hence $I$ is not computable. [/step] [step:Conclude] In both cases ($e \in I$, Step 4; $e \notin I$, Step 5), $I$ is not computable. These cases exhaust the possibilities by the law of excluded middle on $e \in I$. Therefore every non-trivial index set fails to be computable: no non-trivial index set is computable. [/step]