3
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ I am pretty sure that using the fact that $\{e : \varphi_e \text{ is total}\}$ is $\Pi^0_2$ complete, one can also show that the set of fix points for a given total computable $F$ is $\Pi^0_2$ and moreover there exists some total computable $F$ such that the set of $F$-fixed points is $\Pi^0_2$ complete. (I don't however know if every $\Pi^0_2$ set is the set of fixed points of some total computable $F$. That is a more difficult.) $\endgroup$
    – Jason Rute
    Oct 4, 2016 at 15:32
  • 1
    $\begingroup$ This reminds me of a cute paper I saw recently, John Case & Michael Ralston, Non-obfuscated unprovable programs & many resultant subtleties, Log. Methods Comput. Sci. 12 (2016), no. 2, 2:2, 25 pp. lmcs.episciences.org/1634, which deals with a very similar issue (and relates it to provability). $\endgroup$ Oct 4, 2016 at 18:43

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
16
  • $\begingroup$ Yes, this is basically what I already knew, because both Rogers and Odifreddi have this exercise. But my question was more general. Let us forget about pathological functions and take, for instance, $\lambda x.x+1$. I can prove that the set of fixed point values of this $f$ is not recursive. Is it recursively enumerable? What about $\lambda x.x+2$? Are there general theorems about the fixed point values of these functions? $\endgroup$ Oct 4, 2016 at 19:49
  • $\begingroup$ I think that if you are looking at specific functions like that, the answer could depend on the particular way that you represent computable functions by their indices. That is, the answers in those cases may depend on what are usually otherwise considered irrelevant syntactic details. $\endgroup$ Oct 4, 2016 at 20:04
  • $\begingroup$ The acceptable numberings of partial computable functions are pretty robust, why do you think the answers may depend? For instance, the indices of the fixed points of $\lambda x . x + 1$, how could they depend on the numbering in an essential way? $\endgroup$ Oct 4, 2016 at 20:32
  • $\begingroup$ Because the question is not just about the function that the index computes, but it is allowed to ask about the index itself. That is why Rice's theorem, for example, does not apply here. For example, for some enumerations it may be that odd numbers always compute the empty function, and in this case, to decide fixed points of the function $f(i)=2i+1$ will be equivalent to the empty-function problem. $\endgroup$ Oct 4, 2016 at 20:35
  • $\begingroup$ That was my initial thought as well. But on the other hand, the theorem I gave above (i.e., if all orbits have finite complement, then the fixed point set is not recursive) is pretty general, and applies to $\lambda x.x+1$ and any admissible numbering. This suggests that there may be something deeper going on. Are you telling me that this theorem was not known, and that there is no general theory that includes it? $\endgroup$ Oct 4, 2016 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.