lo.logic - Effectively closed computable functions

I like your concept a lot, and have been able to find a characterization.

Suppose that $f:Nto N$ is effectively closed in your sense.

First, as you mentioned, it is easy to see that $text{ran}(f)$ is
computable, since by taking $W_e$ to be empty your equation shows that
$text{ran}(f)$ is both c.e. and co-c.e.

Second, I claim that $f$ is finite-to-one. To see this,
suppose that $f^{-1}(k)$ is infinite for some $k$. Define
a c.e. set $W_e$ as follows: At stage $s$, if we see that
$k$ is still not in $W_{rho(e),s}$, the state-$s$ approximation
to $W_{rho(e)}$, then enumerate the next element of
$f^{-1}(k)$ into $W_e$. (Although this definition may look
circular, since I am defining $W_e$ by reference to
$W_{rho(e)}$, the definition is legitimate by an
application of the Recursion Theorem. That is, I really
define $W_{r(e)}$, and then find $e$ such that $W_e=W_{r(e)}$.)
Note that if $k$ is never enumerated into $W_{rho(e)}$,
then I will eventually put all of $f^{-1}(k)$ into $W_e$,
which will result in $knotin f[N-W_e]$, but $kin
N-W_{rho(e)}$, a contradiction. Alternatively, if $kin
W_{rho(e),s}$, then $f^{-1}(k)cap W_e$ has at most
$s$ members, and so there are $ain N-W_e$ with $f(a)=k$,
placing $k$ into $f[N-W_e]$ but not in $N-W_{rho(e)}$,
again a contradiction.

A similar argument shows actually that the
function $kmapsto f^{-1}(k)$ is computable. Namely,
define the set $W_e$ by the following procedure. At stage
$s$, look at every $kleq s$, and if $knotin
W_{rho(e),s}$, then enumerate all of $f^{-1}(k)cap s$ into
$W_e$. (Again, appeal to Recursion Theorem to get such an
$e$.) In other words, as long as $k$ is not in
$W_{rho(e),s}$, then we put all elements of $f^{-1}(k)$
below $s$ into $W_e$.

If $knotin W_{rho(e)}$, then $f^{-1}(k)subset W_e$, and
so $knotin f[N-W_e]$, contradicting $kin N-W_{rho(e)}$.
Thus, $W_{rho(e)}=N$. From this, it follows that $W_e=N$.
Now, note that $kin W_{rho(e)}$ implies $kin W_{rho(e),s_k}$
for some stage $s_k$, and so $f^{-1}(k)$ is a subset of $s_k$.
By applying $f$ to each value below $s_k$, we see that the
map $kmapsto f^{-1}(k)$ is a computable function.

This means that $f$ has a particularly simple form.
Namely, there is a computable partition $N=bigsqcup_k
B_k$, with each $B_k$ finite, such that $f$ maps elements of
$B_k$ to $k$. (Note that some $B_k$ may be empty.)

Conversely, every function with such a form is
computably closed in your sense. Suppose that $f$ arises
from such a computable partition of $N$ into finite sets
$B_k$. Given any program $e$, enumerate $k$ into $W_{rho(e)}$ when
all of $B_k$ gets enumerated into $W_e$. It follows that
$f[N-W_e]=N-W_{rho(e)}$, as desired.

This provides a characterization of the effectively closed
computable functions:

Theorem. A computable function $f:Nto N$ is
effectively closed if and only if $f$ is finite-to-one and
the map $kmapsto f^{-1}(k)$ is computable.