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).



Effectively non-recursiveness of some sets
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)$.


