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.


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.

| cite | improve this answer | |
  • $\begingroup$ there are other fixed points since $f$ can be a partial function. $\endgroup$ – Kaveh Jan 10 '13 at 2:52
  • $\begingroup$ What are the semantics of $x=y$ and $x=2y$ when $x$ and $y$ could be $\bot$? $\endgroup$ – Yuval Filmus Jan 10 '13 at 8:31
  • $\begingroup$ There are different versions. One version defines them as undefined. $\endgroup$ – Kaveh Jan 10 '13 at 8:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy