parrish@hpisla.HP.COM (Frank Parrish) (01/23/87)
I have been looking for information on the "91 function", a recursive function which always returns a value of 91. Does anyone know the algorithm for this function or a reference where I may find it? Thanks in advance.
kyukawa@watdragon.UUCP (01/25/87)
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. For reference, see Mathematical Theory of Computation, by Z. Manna Chapter 5.
parrish@hpisla.UUCP (01/27/87)
My thanks go out to all of you who responded to my request. I was overwhelmed by the number of responses that I got. Thanks again... Frank.
varghese@milano.UUCP (02/12/87)
>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)
wup@rpics.UUCP (02/12/87)
In article <3782@milano.UUCP>, varghese@mcc.com (Joe Varghese) writes: > ...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). > This works only for X=10*N+1 for integer N. Other cases the program goes into infinite recursion... try f91(100,Y). I suppose the third clause should have been f91(X,Y) :- X > 100, !, Z is X - 11, f91(Z,Y). Then it will work... Peter Y.F. Wu wup@csv.rpi.edu
varghese@milano.UUCP (02/18/87)
In article <3782@milano.UUCP>, varghese@milano.UUCP writes: > > 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 last line of the prolog version should be f91(X,Y) :- Z is X + 11, f91(Z,W), f91(W,Y). to make it correspond to the Lisp version. I work on Lisp machines and the Prolog version is a translation of the Lisp program. Sorry about that. -------------------- Joe Varghese varghese@mcc.com