Kleene's fixed point theorem on recursive subsets of computable functions

Question

I have a question about the possibility to apply/restate the Kleene fixed point theorem on recursive subsets of computable functions. I don't know if this is trivial and/or if related questions have been already solved. Any suggestion is more than welcome.

Kleene fixed point theorem states that for every total computable function $T_i \simeq \varphi:\mathbb{N}\rightarrow \mathbb{N}$ there exists some $v\in\mathbb{N}$ such that $\forall x, T_{\varphi(v)}(x)\simeq T_v(x)$. That is, the $v$-th ($T_v$) Turing Machine (TM) computes the same function as the $\varphi(v)$-th TM, and $v$ is thus a "fixed point" for the transformation $\varphi$.

Consider now a total computable function $f:\mathbb{N}\rightarrow \mathbb{N}$. The recursive (infinite) set $E=f(\mathbb{N})$ represents the subset of TMs/computable functions, $T_{f(1)}, T_{f(2)}, ..$, we want to consider. Since $E$ is a recursive set, we can use the notation $T^E_i$ to denote $T_{f(i)}$, i.e. $T^E_i$ is the i-th TM/function in $E$. Let $T^E_{i}\simeq\phi$ be a total computable function (if any). Now, it is possible to restate the Kleene fixed point theorem on the set $E$? That is, is it true that there exists some $v\in \mathbb{N}$ such that: $\forall x: T^E_{\phi(v)}(x)\simeq T^E_{v}(x)$? Note that we cannot apply here directly the Kleene's theorem since the property above translates into $\exists v \forall x: T_{f(\phi(v))}(x)\simeq T_{f(v)}(x)$ and the original (standard?) proof seems hard (if not impossible) to recode in this new setting (unless $f$ is assumed to be surjective, in which case the problem becomes trivial).

I don't expect this property to be true for all the possible recursive functions $f$ (it's just my non-expert opinion), so my question is: is it possible to characterize the class of mappings $f$ for which the above property is true? For example, is this property true if we assume that the range of $f$ is a set of total functions?

Answer 1

In general, there will be no such fixed points, even when the range of $f$ consists of programs for total computable functions. The reason is that we can easily compute a list of programs for distinct total functions. That is, we can arrange that $T_{f(n)}\neq T_{f(m)}$ whenever $n\neq m$. For example, we could for each $n$ let $f(n)$ be a program that computes the constant value $n$ function, which would certainly achieve $T_{f(n)}\neq T_{f(m)}$. The point about this now is that if $\varphi$ is a computable function such that $\varphi(v)\neq v$ for every $v$, such as the successor function $\varphi(v)=v+1$, then it follows that $T_{f(\varphi(v))}\neq T_{f(v)}$, and so there is no fixed point in your sense.

Edit. François pointed out in the comments that you want $\varphi$ among the $T_{f(n)}$, a feature my particular example above does not have. But this is easily fixed. Let's use $T_{f(n)}(x)=x+n$ instead, and consider $\varphi(v)=v+1$, which is $T_{f(1)}$. The point, as above, is that $\varphi(v)\neq v$ and so also $T_{f(\varphi(v))}\neq T_{f(v)}$. Thus, there is no fixed point.

Answer 2

There are some very strong counterexamples to this, which illustrate the importance of so-called acceptable enumerations of partial recursive functions. Joel gave a nice one with total recursive functions, here is another striking counterexample due to Friedberg [Three theorems on recursive enumeration, JSL 23 (1953), 309-316, MR0109125].

Friedberg showed that there is a uniformly recursive one-to-one enumeration of the partial recursive functions; this is now known as a Friedberg enumeration. In other words, there is a recursive function $f$ such that every partial recursive function occurs exactly once in the listing $T_{f(0)},T_{f(1)},T_{f(2)},\ldots$. This function $f$ will necessarily fail to have fixed points.

(Unfortunately, there is no recursive enumeration of all total recursive functions at all, so there is no such strong counterexample with this added restriction.)