[proofplan] We use Cantor-style diagonalisation. Assume for contradiction that $\mathbb{K}$ is computable, so its indicator function is a total computable function. Build a computable partial function $f : \mathbb{W} \rightharpoonup \mathbb{W}$ that diverges on $w$ iff $f_{w, 1}(w)$ halts — the "flipped halting behaviour" — using the computable indicator to branch. By the definition of computability, $f = f_{d, 1}$ for some code $d \in \mathbb{W}$. Evaluating at the code $d$ of $f$ itself gives $f_{d, 1}(d) \downarrow \iff f_{d, 1}(d) \uparrow$, a contradiction. This proves $\mathbb{K}$ is not computable. For $\mathbb{K}_0$, we observe that if $\mathbb{K}_0$ were computable, we would obtain computability of $\mathbb{K}$ by precomposition with the computable diagonal $\Delta(w) = (w, w)$ (the preimage of a computable set under a total computable map is computable), contradicting the first part. Hence $\mathbb{K}_0$ is not computable either. [/proofplan] [step:Fix notation and state what "computable set" means] With $\mathbb{W} = \Sigma^*$ and the course's $\operatorname{code}$-convention as in Step 1 of the proof of [Halting Sets Are Computably Enumerable](/theorems/1822), define \begin{align*} \mathbb{K}_0 &:= \{(w, v) \in \mathbb{W}^2 : f_{w, 1}(v) \downarrow\}, \\ \mathbb{K} &:= \{w \in \mathbb{W} : f_{w, 1}(w) \downarrow\}. \end{align*} Recall that a set $X \subseteq \mathbb{W}^k$ is *computable* iff its indicator function \begin{align*} \mathbb{1}_X : \mathbb{W}^k &\to \mathbb{W}, \\ w &\mapsto \begin{cases} a & \text{if } w \in X, \\ \varepsilon & \text{if } w \notin X \end{cases} \end{align*} is a total computable function, where $a \in \Sigma$ is a fixed distinguished "accept" letter (as in the proof of [Truncated Computation Function](/theorems/1819)). Our goal is to show that neither $\mathbb{K}$ nor $\mathbb{K}_0$ is computable. [/step] [step:Diagonalise to derive a contradiction from the assumption that $\mathbb{K}$ is computable] Suppose for contradiction that $\mathbb{K}$ is computable. Then $\mathbb{1}_\mathbb{K} : \mathbb{W} \to \mathbb{W}$ is total computable. Define an auxiliary partial function \begin{align*} f : \mathbb{W} &\rightharpoonup \mathbb{W}, \\ w &\mapsto \begin{cases} \uparrow & \text{if } \mathbb{1}_\mathbb{K}(w) = a, \\ \varepsilon & \text{if } \mathbb{1}_\mathbb{K}(w) = \varepsilon. \end{cases} \end{align*} Equivalently, $f(w) \downarrow = \varepsilon$ iff $w \notin \mathbb{K}$, and $f(w) \uparrow$ iff $w \in \mathbb{K}$. [claim:$f$ is computable] We construct a register machine $M_f$ realising $f$. On input $w$ in register $0$: (a) *Compute $\mathbb{1}_\mathbb{K}(w)$.* Save a master copy of $w$ to a scratch register (optional — we do not need $w$ again, but the standard concatenation pattern preserves inputs for robustness). Invoke the register machine witnessing $\mathbb{1}_\mathbb{K}$ (which exists by the hypothesis that $\mathbb{K}$ is computable) on input register $0$. It halts with register $0$ holding either $a$ or $\varepsilon$. (b) *Branch on the result.* Read the sole letter of register $0$ using the register-machine's letter-test instruction. Two branches: - If the letter read is $a$ (case $\mathbb{1}_\mathbb{K}(w) = a$), enter a state $q_\text{loop}$ whose sole instruction transitions back to $q_\text{loop}$ (a divergent loop). $M_f$ runs forever, matching $f(w) \uparrow$. - If the read returns $\varepsilon$ (case $\mathbb{1}_\mathbb{K}(w) = \varepsilon$), erase register $0$ (to ensure output is $\varepsilon$) and transition to the halt state. $M_f$ halts with output $\varepsilon$, matching $f(w) = \varepsilon$. Each step is either a finite fixed sub-routine or a single register-machine instruction. The branch in (b) is a standard hard-wired case distinction on the result of a letter read. Hence $M_f$ computes $f$, so $f$ is computable. [/claim] Since $f$ is computable, there exists a register machine $D$ of arity $1$ with $f_{D, 1} = f$. Let $d := \operatorname{code}(D) \in \mathbb{W}$, so that (in the course's shorthand) $f_{d, 1} = f$. Now we evaluate the definition of $f$ at the specific input $w = d$ and compare the two equivalent characterisations of membership in $\mathbb{K}$: \begin{align*} f(d) \downarrow &\iff f_{d, 1}(d) \downarrow \tag{since $f = f_{d, 1}$} \\ &\iff d \in \mathbb{K} \tag{definition of $\mathbb{K}$} \\ &\iff \mathbb{1}_\mathbb{K}(d) = a \tag{definition of $\mathbb{1}_\mathbb{K}$} \\ &\iff f(d) \uparrow. \tag{definition of $f$, $\mathbb{1}_\mathbb{K}$-branch} \end{align*} The chain yields $f(d) \downarrow \iff f(d) \uparrow$, which is a contradiction (the two conditions are exhaustive and mutually exclusive: a partial function is either defined at a point or undefined at it). Hence the assumption that $\mathbb{K}$ is computable is false, so $\mathbb{K}$ is not computable. [/step] [step:Deduce non-computability of $\mathbb{K}_0$ by reducing to $\mathbb{K}$] Suppose for contradiction that $\mathbb{K}_0$ is computable, so $\mathbb{1}_{\mathbb{K}_0} : \mathbb{W}^2 \to \mathbb{W}$ is total computable. Define \begin{align*} \Delta : \mathbb{W} &\to \mathbb{W}^2, \\ w &\mapsto (w, w), \end{align*} which is total computable (each coordinate is the identity on $\mathbb{W}$; see Step 3 of the proof of [Halting Sets Are Computably Enumerable](/theorems/1822)). Consider the composition \begin{align*} g : \mathbb{W} &\to \mathbb{W}, \\ w &\mapsto \mathbb{1}_{\mathbb{K}_0}(\Delta(w)) = \mathbb{1}_{\mathbb{K}_0}(w, w). \end{align*} As a composition of total computable functions, $g$ is total computable by L1 in Step 4 of the proof of [Recursive Implies Computable](/theorems/1817). We compute $g(w)$ for $w \in \mathbb{W}$: \begin{align*} g(w) = a &\iff \mathbb{1}_{\mathbb{K}_0}(w, w) = a \iff (w, w) \in \mathbb{K}_0 \iff f_{w, 1}(w) \downarrow \iff w \in \mathbb{K}, \\ g(w) = \varepsilon &\iff \mathbb{1}_{\mathbb{K}_0}(w, w) = \varepsilon \iff (w, w) \notin \mathbb{K}_0 \iff f_{w, 1}(w) \uparrow \iff w \notin \mathbb{K}, \end{align*} where we used the defining equivalences of $\mathbb{K}_0$ and $\mathbb{K}$ from Step 1. Hence $g = \mathbb{1}_\mathbb{K}$. But $g$ is total computable, so $\mathbb{1}_\mathbb{K}$ is total computable, i.e. $\mathbb{K}$ is computable. This contradicts Step 2. Hence $\mathbb{K}_0$ is not computable. [/step] [step:Conclude] By Step 2, $\mathbb{K}$ is not computable. By Step 3, $\mathbb{K}_0$ is not computable. This proves the theorem. [/step]