Computability of sets of fixed point values

Question

Recall that Rogers' fixed point theorem states that, if $f$ is a total computable function, then it has a fixed point value, i.e., there is an index $i$ such that $\varphi_i\simeq\varphi_{f(i)}$.

My question is what is known about the recursiveness and recursive enumerability of the set of fixed point values of $f$.

I can prove, for instance, that if the orbit (under $f$) of each index has finite complement (with respect to $\mathbb N$), then the set of fixed point values of $f$ is not recursive. The techniques I used have been around since the works of Kleene, hence my results should be well known. Still, I was unable to find any discussion on this topic in the relevant literature, except for a couple of exercises on Rogers' and Odifreddi's monographs, which seem to hint at a well-developed theory, but provide no specific references.

Any pointers?

EDIT: to make my question more concrete, let us focus on the function $f=\lambda x.x+1$. I know that the set $F$ of the fixed point values of $f$ is not recursive, for any admissible numbering of computable functions. What about recursive enumerability? Are there two admissible numberings that make $F$ r.e. and not r.e., respectively?

Answer 1

In general, the question of whether a given program $i$ is a fixed-point with respect to a given computuble function $f$, has complexity $\Pi^0_2$. And for some functions, it is $\Pi^0_2$-complete.

First, it is easy to see that the assertion that $i$ is a fixed point with respect to $f$, meaning that $\varphi_i=\varphi_{f(i)}$, has complexity at most $\Pi^0_2$, since $i$ is a fixed point just in case for every converging instance of one of the functions, there is a corresponding converging instance of the other with the same output value.

Conversely, let me provide a computable function $f$ for which the fixed-point set is $\Pi^0_2$-complete. Fix a $\Pi^0_2$-universal set $U$, where $x\in U$ if and only if $\forall k\ \exists j\ A(x,k,j)$, where $A$ is $\Delta_0$. Define $f$ as follows. For each $i$, let $f(i)$ be a program undertaking the following procedure: first, let $x=\varphi_i(0)$; now, on input $k$, search for $j$ for which $A(x,k,j)$, and output $x$ if found; otherwise keep searching.

For any $x$, let $e_x$ be a program that is known to compute constant value $x$. Observe that $x\in U$ just in case $f(e_x)$ computes the constant value $x$. Thus, $x\in U$ if and only if $e_x$ computes the same function as $f(e_x)$, which is to say, if and only if $e_x$ is a fixed point with respect to $f$.

So for this function, the fixed-point set is $\Pi^0_2$-complete. In particular, it is not c.e.

Update. Meanwhile, let us consider your updated question, focussed on the particular function $s(x)=x+1$. I claim that there is an admissible enumeration of computable functions for which the fixed-point question for this function is is not c.e. Suppose for example that we have an encoding where odd numbers always encode the empty function. (Many of the naturally occurring encodings of Turing machines or whatever have this property, if you use, say, prime powers for sequence encoding or $2^n(2m+1)$-type pairing functions, since odd numbers wouldn't code things as usual, and the corresponding enumerated computable function $\varphi_k$ for $k$ odd would be the empty function by default.) Thus, a fixed point $\varphi_e=\varphi_{e+1}$ for the successor function in this case would involve at least one odd index, and so it would be the empty function. Thus, an index $e$ is a fixed point if and only if $e$ is even and $\varphi_e$ is the empty function, or $e$ is odd and $\varphi_{e+1}$ is the empty function. This is easily seen to be co-c.e. and $\Pi^0_1$-complete, using methods as in my answer above. Basically, it is equivalent to the emptiness problem, which is $\Pi^0_1$-complete. In particular, it is not c.e.