# Fixpoints of a transformation of an extended WHILE program

I am doing some excercises to train myself in computability. There is one that I am not able to solve, here it is.

Consider the following transformation associated to an extended WHILE program:

For all $x \in \mathbb{N}$, $\begin{cases} A f(x) = x \cdot f((x+3)/2) & \text{if $$x$$ is odd} \\ A f(x) = f(x+1) & \text{otherwise} \\ \end{cases}$

1. How many fixed points does $A$ have?
2. Is there a maximum fixed point?
3. Find the minimum fixed point.

I know that a fixed point is a function $f$ such as $A f = f$.

I would say there is an infinite fixed point. But how to prove it?

To calculate the minimum, I would make a table with on each row: $\bot$, $A \bot$, $A^2 \bot$, ... and if there are two similar lines, that's our minimum. But once again I am not sure this is enough to do this.

-

## migrated from cstheory.stackexchange.comJan 8 '13 at 20:25

This question came from our site for theoretical computer scientists and researchers in related fields.

Suppose $f$ is a fixpoint of $A$. First, $$f(0) = f(1) = f(2) = f(3) = 3f(3),$$ and so $f(0) = f(1) = f(2) = f(3) = 0$. Second, $$f(5) = 5f(4) = 5f(5),$$ and so $f(4) = f(5) = 0$. Third, if $n = 4m+3 \geq 7$ then $$f(n) = n f(2m+3),$$ while if $n = 4m+1 \geq 9$ then $$f(n) = n f(2m+2) = nf(2m+3).$$ In both cases, $2m+3 < n$, and so you can prove by induction that $f(n) = 0$ for all odd $n$. That implies that $f(n) = 0$ also for all even $n$, and we conclude that $f(n) = 0$ for all $n$.
Edit: This is the maximal fixpoint. The minimal fixpoint is $\bot$. There are two other fixpoints: $f(n) = 0$ for $n \leq 3$ and undefined otherwise, and $f(n) = 0$ for $n > 3$ and undefined otherwise.
there are other fixed points since $f$ can be a partial function. –  Kaveh Jan 10 '13 at 2:52
What are the semantics of $x=y$ and $x=2y$ when $x$ and $y$ could be $\bot$? –  Yuval Filmus Jan 10 '13 at 8:31