[proofplan] We use the productive function for the complement of $C$ to turn each possible self-halting computation $\varphi_e(e)$ into a number whose membership in $C$ exactly records whether that computation halts. The recursion theorem with parameters supplies, uniformly in $e$, an index $q(e)$ for a computably enumerable set that either stays empty or enumerates the single number $p(q(e))$. Productivity then forces $p(q(e))$ to lie outside $C$ in the nonhalting case and inside $C$ in the halting case. This gives a total computable many-one reduction $e \mapsto p(q(e))$ from $K$ to $C$, and the Turing equivalence follows because every computably enumerable set is Turing reducible to $K$. [/proofplan] [step:Use the recursion theorem to build the self-referential indices] Let $p: \mathbb{N} \to \mathbb{N}$ be a total computable productive function for $C$ in the sense of the statement. We apply the recursion theorem with parameters (citing a result not yet in the wiki: Kleene Recursion Theorem with Parameters) to the following uniform effective construction. For each pair $(e,a) \in \mathbb{N}^2$, define a partial computable enumeration procedure $M_{e,a}$ as follows: on no input, the procedure waits for the computation $\varphi_e(e)$ to halt; if $\varphi_e(e)$ halts, it enumerates the single number $p(a)$, and if $\varphi_e(e)$ never halts, it enumerates no number. Since $p$ is total computable, the map \begin{align*} (e,a) \mapsto \text{an index for the c.e. set enumerated by } M_{e,a} \end{align*} is total computable. By the recursion theorem with parameters, there is a total computable function \begin{align*} q: \mathbb{N} &\to \mathbb{N} \end{align*} such that, for every $e \in \mathbb{N}$, the c.e. set $W_{q(e)}$ is exactly the set enumerated by $M_{e,q(e)}$. Therefore, for every $e \in \mathbb{N}$, \begin{align*} W_{q(e)} = \begin{cases} \varnothing, & \text{if } \varphi_e(e)\uparrow,\\ \{p(q(e))\}, & \text{if } \varphi_e(e)\downarrow. \end{cases} \end{align*} [guided] The obstacle is that the productive function must be applied to an index of a c.e. set, but the set we want to define must itself mention the value obtained by applying $p$ to that same index. The recursion theorem is precisely the tool that permits this controlled self-reference. Define, uniformly in parameters $(e,a) \in \mathbb{N}^2$, a c.e. set as follows. The procedure $M_{e,a}$ watches the computation $\varphi_e(e)$. If this computation never halts, the procedure never enumerates anything. If the computation halts, the procedure enumerates exactly one number, namely $p(a)$. This is an effective construction because $p$ is a total computable function, so whenever the parameter $a$ is given, the value $p(a)$ can be computed before being enumerated. The recursion theorem with parameters now supplies a total computable function \begin{align*} q: \mathbb{N} &\to \mathbb{N} \end{align*} with the fixed-point property that $q(e)$ is an index for the procedure obtained by substituting $a = q(e)$ into the preceding construction. Thus the c.e. set $W_{q(e)}$ behaves as follows: it waits for $\varphi_e(e)$, and if that computation halts it enumerates $p(q(e))$. Consequently, for each $e \in \mathbb{N}$, there are exactly two cases: \begin{align*} W_{q(e)} = \begin{cases} \varnothing, & \text{if } \varphi_e(e)\uparrow,\\ \{p(q(e))\}, & \text{if } \varphi_e(e)\downarrow. \end{cases} \end{align*} The point of this construction is that the same index $q(e)$ appears both as the index of the set and as the input to the productive function. That is the self-reference needed for the contradiction in the halting case. [/guided] [/step] [step:Show that nonhalting inputs are sent outside $C$] Fix $e \in \mathbb{N}$ and suppose $\varphi_e(e)\uparrow$. By the description of $W_{q(e)}$ obtained above, \begin{align*} W_{q(e)} = \varnothing. \end{align*} Since $\varnothing \subset \mathbb{N} \setminus C$, the defining productivity property of $p$ applied to the index $q(e)$ gives \begin{align*} p(q(e)) \in \mathbb{N} \setminus C. \end{align*} Thus, if $e \notin K$, then $p(q(e)) \notin C$. [/step] [step:Show that halting inputs are sent inside $C$] Fix $e \in \mathbb{N}$ and suppose $\varphi_e(e)\downarrow$. By the description of $W_{q(e)}$, \begin{align*} W_{q(e)} = \{p(q(e))\}. \end{align*} Assume, toward a contradiction, that $p(q(e)) \notin C$. Then \begin{align*} W_{q(e)} = \{p(q(e))\} \subset \mathbb{N} \setminus C. \end{align*} Applying the productivity property of $p$ to the index $q(e)$ gives \begin{align*} p(q(e)) \notin W_{q(e)}. \end{align*} But $W_{q(e)} = \{p(q(e))\}$, so \begin{align*} p(q(e)) \in W_{q(e)}. \end{align*} This contradiction shows that $p(q(e)) \in C$. Hence, if $e \in K$, then $p(q(e)) \in C$. [guided] Here the self-reference from the recursion theorem is used to force membership in $C$. Suppose $\varphi_e(e)$ halts. Then the construction of $W_{q(e)}$ has actually enumerated the single number $p(q(e))$, so \begin{align*} W_{q(e)} = \{p(q(e))\}. \end{align*} We want to prove that $p(q(e)) \in C$. Assume the opposite, namely $p(q(e)) \notin C$. Under this assumption the only element of $W_{q(e)}$ lies outside $C$, and therefore \begin{align*} W_{q(e)} \subset \mathbb{N} \setminus C. \end{align*} Now the productivity hypothesis applies to the index $q(e)$. It says that whenever $W_{q(e)}$ is contained in the complement of $C$, the number $p(q(e))$ must avoid $W_{q(e)}$: \begin{align*} p(q(e)) \notin W_{q(e)}. \end{align*} But this is impossible, because in the halting case $W_{q(e)}$ was defined to be the singleton $\{p(q(e))\}$. Hence \begin{align*} p(q(e)) \in W_{q(e)}. \end{align*} The contradiction comes exactly from asking the productive function to produce a new element outside a set that has already been arranged to contain that very element. Therefore the assumption $p(q(e)) \notin C$ is false, and $p(q(e)) \in C$. [/guided] [/step] [step:Define the many-one reduction from $K$ to $C$] Define \begin{align*} f: \mathbb{N} &\to \mathbb{N} \\ e &\mapsto p(q(e)). \end{align*} The function $q$ is total computable by the recursion theorem with parameters, and $p$ is total computable by hypothesis, so $f = p \circ q$ is total computable. Combining the two preceding steps, for every $e \in \mathbb{N}$, \begin{align*} e \in K &\iff \varphi_e(e)\downarrow \\ &\iff p(q(e)) \in C \\ &\iff f(e) \in C. \end{align*} Thus $f$ is a many-one reduction from $K$ to $C$, and therefore \begin{align*} K \le_m C. \end{align*} [/step] [step:Conclude Turing equivalence with the halting set] Since $K \le_m C$, we immediately have $K \le_T C$, because a many-one reduction is a special case of a Turing reduction. It remains to show $C \le_T K$. Since $C$ is computably enumerable, fix an index $c \in \mathbb{N}$ such that \begin{align*} C = W_c. \end{align*} Using the standard parameter theorem for computable functions (citing a result not yet in the wiki: $s$-$m$-$n$ Theorem), there is a total computable function \begin{align*} r: \mathbb{N} &\to \mathbb{N} \end{align*} such that, for every $x \in \mathbb{N}$, the computation $\varphi_{r(x)}(r(x))$ halts exactly when the enumeration of $W_c$ eventually lists $x$. Hence \begin{align*} x \in C &\iff x \in W_c \\ &\iff \varphi_{r(x)}(r(x))\downarrow \\ &\iff r(x) \in K. \end{align*} Therefore $C \le_m K$, and in particular $C \le_T K$. Combining $K \le_T C$ and $C \le_T K$, we obtain \begin{align*} C \equiv_T K. \end{align*} This completes the proof. [/step]