🚀 go-pugleaf

>From: Frank Parrish <hpcea!hpisla!parrish@hplabs.hp.com>
>
>I have been looking for information on the "91 function", a recursive
>function which always returns a value of 91.  


>From: Keitaro Yukawa <kyukawa@rutgers.rutgers.edu> 
>
>The 91 function was cooked up by J. McCarthy and is defined as:
>F(x) = if x > 100 then x-10 else F(F(x+11)),
>whose least fixpoint is:
>f(x) = if x > 100 then x-10 else 91.
>So it doesn't always return 91.  It has been used for exercises in
>recursive program schemata and program verification. 

A "fix" to make it converge to 91:

(defun f91 (x) 
  (cond ((= x 91) 91)
	((> x 111) (f91 (f91 (- x 10))))
	((> x 100) (f91 (- x 10)))
	(t (f91 (f91 (+ x 11))))))

or, if you don't speak LISP, a Prolog version:

f91(91,91) :- !.
f91(X,Y) :- X > 111, !, Z is X - 10, f91(Z,W), f91(W,Y).
f91(X,Y) :- X > 100, !, Z is X - 10, f91(Z,Y).
f91(X,Y) :- Z is X + 10, f91(Z,W), f91(W,Y).

{The engineer's fix:  (defun f91 (x) 91)   }


-----------------
Joe Varghese
varghese@mcc.com                           (ARPA)
...!seismo!ut-sally!im4u!milano!varghese   (UUCP)