Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!utgpu!water!watnot!watmath!clyde!rutgers!im4u!milano!varghese From: varghese@milano.UUCP Newsgroups: comp.lang.prolog Subject: Re: 91 function Message-ID: <3782@milano.UUCP> Date: Wed, 11-Feb-87 21:11:24 EST Article-I.D.: milano.3782 Posted: Wed Feb 11 21:11:24 1987 Date-Received: Fri, 13-Feb-87 00:37:24 EST Sender: varghese@milano.UUCP Organization: MCC, Austin, TX Lines: 39 >From: Frank Parrish > >I have been looking for information on the "91 function", a recursive >function which always returns a value of 91. >From: Keitaro Yukawa > >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)