Let $\phi$ be an acceptable programming system. For every recursive function $f$, let $(f)=\{x:\phi\_x=\phi\_{f(x)}\}$ the set of fixed points of $f$. Now, suppose that $f$ and $g$ are recursive functions such that $(f)$ and $(g)$ are disjoint sets. The question is: are there recursive functions $F$ and $G$ such that $(F)\subseteq(f)$, $(G)\subseteq(g)$ and $\phi\_{F(x)}\neq\phi\_{G(x)}$, for all $x$?



Disjoint sets of fixed points
This turns out to be false. I'll construct $f$ and $g$ that there are no $F$ and $G$ with the required properties.


Define $f$ such that for any $x$,


1. $\phi\_{f(x)}(0) = 0$
2. If $\phi\_x(0)$ has halted by $n$ steps then $\phi\_{f(x)}(n) = 0$
3. If $\phi\_x(0)$ has not halted by $n$ steps then $\phi\_{f(x)}(n)$ is undefined


So the fixed points $x$ of $f$ are such that $\phi\_x(0)$ is defined and equal to 0 and for large enough $n>0$, also $\phi\_x(n)$ is defined and equal to 0.


Define $g$ such that for all $x$, $\phi\_{g(x)}(0) = 0$ and $\phi\_{g(x)}(n)$ is undefined for $n > 0$. The fixed points of $g$ are defined at 0 but then undefined thereafter, so $f$ and $g$ don't have any fixed points in common.


Now suppose for a contradiction that there are $F$ and $G$ with the required properties.


We define $x$ using the fixed point theorem so that $x$ encodes the program that feeds its own code to $F$ and $G$ to find $F(x)$ and $G(x)$ and then starts simultaneously checking for the following conditions


1. there exists $n$ such that $\phi\_x(n) \downarrow$
2. $\phi\_{F(x)}(0)$ is defined but not equal to 0
3. there exists $n > 0$ such that $\phi\_{F(x)}(n) \downarrow$
4. $\phi\_{G(x)}(0)$ is defined but not equal to 0
5. there exists $n > 0$ such that $\phi\_{G(x)}(n) \downarrow$


If condition 1 is ever matched, then there is some $n,m$ such that $\phi\_x(n) = m$. Define $x$ so that at this point it stops checking for the conditions and halts with output $m + 1$ (on any input, but in particular on input $n$).


Define $x$ so that if condition 2 is ever matched then $x$ stops checking for the conditions and switches to copying $F(x)$, ie on input $n$, $x$ outputs $\phi\_F(x)(n)$.


If condition 3 is matched then for some $n$, $\phi\_{F(x)} \downarrow$. "Loop round" $n$ times (to ensure that $x$ does not halt in less than $n$ steps) and then start copying $F(x)$ like before.


Define $x$ so that if condition 4 or 5 is ever matched then $x$ stops checking for the conditions and switches to copying $G(x)$, ie on input $n$, $x$ outputs $\phi\_G(x)(n)$.


We now check that none of these conditions can ever actually be satisfied. For condition 1 it is clear.


For condition 2, note that if it is ever matched, then $x$ is a fixed point of $F$ and hence of $f$, but also $\phi\_x(0) \neq 0$. Contradiction.


For condition 3, note that if it is satisfied, then $x$ is a fixed point of $F$ and hence of $f$ and also that for some $n$ $\phi\_x(n) \downarrow$ but that $\phi\_x(0)$ requires more than $n$ steps to halt. Again this is a contradiction.


If conditions 4 or 5 is matched, this implies that $x$ is a fixed point of $g$, similarly giving a contradiction.


Now we know that none of the conditions are ever matched, we can deduce the following:


1. for all $n$, $\phi\_x(n) \uparrow$
2. if $\phi\_{F(x)}(0) \downarrow$ then $\phi\_{F(x)}(0) = 0$
3. for $n>0$, $\phi\_{F(x)}(n) \uparrow$
4. if $\phi\_{G(x)}(0) \downarrow$ then $\phi\_{G(x)}(0) = 0$
5. for $n>0$, $\phi\_{G(x)}(n) \uparrow$


Finally note that if $\phi\_{F(x)}(0) \uparrow$, then $\phi\_{F(x)}$ is undefined everywhere, and hence equal to $\phi\_x$. But this would make it a fixed point of $f$ that is undefined at 0, so we get a contradiction. Similarly, $\phi\_{G(x)}(0)$ must be defined.


Therefore $\phi\_{F(x)}$ and $\phi\_{G(x)}$ are both equal to the partial function that is 0 at 0 and undefined thereafter.


