Question

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$?

Answer 1

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.