Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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