Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!watnot!watdragon!kyukawa
From: kyukawa@watdragon.UUCP
Newsgroups: comp.lang.prolog
Subject: Re: 91 function
Message-ID: <2168@watdragon.UUCP>
Date: Sat, 24-Jan-87 20:54:48 EST
Article-I.D.: watdrago.2168
Posted: Sat Jan 24 20:54:48 1987
Date-Received: Sun, 25-Jan-87 05:36:33 EST
Distribution: comp
Organization: U of Waterloo, Ontario
Lines: 15
Keywords: recursive program schemata, program verification


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.