Fixed Points

• If we could find a fixed point of R, we would be done

• How can we find fixed points?

• ``And then, a miracle occurs...''

• There is a function, Y, which computes fixed points.

• For any f, (Y f) is a fixed point of f

        fix = Y f
        (f fix) = fix

• Or, more succinctly,

        (f (Y f)) = (Y f)

• !!!

Next

Copyright © 1999 M-J. Dominus