Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
add comment

migrated from cstheory.stackexchange.com Jan 8 '13 at 20:25

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

1 Answer

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.

share|improve this answer
    
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
    
There are different versions. One version defines them as undefined. –  Kaveh Jan 10 '13 at 8:32
add comment

Your Answer

 
discard

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