Effectively non-recursiveness of some sets A set $A$ is completely productive if there exists a computable function $f$ such that for every $e$, $f(e)\in (A-W_e)\cup (W_e-A)$‎. ‎A set is effectively non-recursive if it is r.e‎. ‎and its complement is completely productive (see Odifereddi's Classical recursion theory, ‎p.304)‎.
The set $K=\{n:~n\in W_n\}$ ‎and many other natural examples of non-recursive sets are in fact effectively non-recursive‎. ‎A natural example of an r.e set which is not effectively non-recursive is the set $\{n:~K(n)<n\}$‎, ‎where $K(x)=\mu y\,[\varphi_y(0)\!\downarrow=x]$ is a Kolmogorov complexity function‎. ‎
‎Question: Is the set $\{\langle m,n\rangle:‎~ ‎K(m)<n\}$‎ effectively non-recursive?‎ (where $\langle -,-\rangle$ is a standard pairing function).
 A: It's not. Let $A$ be the complement of this set, and suppose that $f$ witnesses that $A$ is completely productive. Let $S$ be an infinite, computable set of indices that we control (via the Recursion Theorem), and let $i \notin S$ be another index that we control.
Define $W_e$ as follows. If $f(e)=\langle m,n \rangle$ for some $n>i$ and $e \in S$, then let $W_e = \emptyset$. Otherwise, if $f(e)=f(e')$ for some $e'<e$ with $e' \in S$, then let $W_e = \emptyset$. If neither of these cases holds, then let $W_e=\{f(e)\}$.
If there is an $e$ such that $f(e)=\langle m,n \rangle$ for some $n>i$, then let $\varphi_i(0)$ be the corresponding $m$ for the least such $e$. Otherwise let $\varphi_i(0)$ be undefined.
Now there are three cases.
Case 1. There is an $e \in S$ such that $f(e)=\langle m,n \rangle$ for some $n>i$. Then for the least such $e$, we have ensured that $f(e) \notin A$ and $f(e) \notin W_e$.
Case 2. Not case 1, and there is an $n$ such that $\{m : \langle m,n \rangle \in f(S)\}$ is infinite. If we choose a large enough $m$ in this set, then $\langle m,n \rangle \in A$. Thus for the least $e \in S$ such that $f(e) =\langle m,n \rangle$, we have $f(e) \in A$ and $f(e) \in W_e$.
Case 3. Neither of the above cases holds. Then there must be $e'<e$ such that $e',e \in S$ and $f(e')=f(e)$, but $f(e'') \neq f(e)$ for all $e''<e'$ with $e'' \in S$. Then $f(e) \in W_{e'}$ but $f(e) \notin W_e$. Thus we get a contradiction whether $f(e) \in A$ or not.
Edit: To be more precise about the definition of $S$ and $i$, what we actually do is define a computable binary function $g$ as follows. Given $j$, for each $e>0$ in order, let $g(j,e)$ be a number $k$ such that $k>g(j,e')$ for $0<e'<e$ and $W_k$ acts as follows: Until $\varphi_j(e')$ converges for all $e' \leqslant e$, no number enters $W_k$. If $f(\varphi_j(e)) = \langle m,n \rangle$ for some $n \leqslant \varphi_j(0)$ and $f(\varphi_j(e)) \neq f(\varphi_j(e'))$ for all $e' < e$ then $f(\varphi_j(e))$ enters $W_k$. Otherwise, no number enters $W_k$. Let $g(j,0)$ be an $l$ such that $\varphi_l(0)=m$ for the $m$ corresponding to the least $e>0$ such that $f(\varphi_j(e))=\langle m,n \rangle$ with $n>\varphi_j(0)$ if there is such an $e$, and $\varphi_l(0)$ diverges otherwise. Notice that $g$ is total. By the Second Recursion Theorem, there is a $j$ such that $\varphi_j(e)=g(j,e)$ for all $e$. Let $S=\{g(j,e) : e>0\}$ and let $i=g(j,0)$.
