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?
Best Answer
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.