McCarthy 91 function


The McCarthy 91 function is a recursive function, defined by the computer scientist John McCarthy as a test case for formal verification within computer science.
The McCarthy 91 function is defined as
The results of evaluating the function are given by M = 91 for all integer arguments n ≤ 100, and M = n − 10 for n > 100. Indeed, the result of M is also 91. All results of M after n = 101 are continually increasing by 1, e.g. M = 92, M = 93.

History

The 91 function was introduced in papers published by Zohar Manna, Amir Pnueli and John McCarthy in 1970. These papers represented early developments towards the application of formal methods to program verification. The 91 function was chosen for being nested-recursive. The example was popularized by Manna's book, Mathematical Theory of Computation. As the field of Formal Methods advanced, this example appeared repeatedly in the research literature.
In particular, it is viewed as a "challenge problem" for automated program verification.
It is easier to reason about tail-recursive control flow, this is an equivalent definition:
As one of the examples used to demonstrate such reasoning, Manna's book includes a tail-recursive algorithm equivalent to the nested-recursive 91 function. Many of the papers that report an "automated verification" of the 91 function only handle the tail-recursive version.
This is an equivalent mutually tail-recursive definition:
A formal derivation of the mutually tail-recursive version from the nested-recursive one was given in a 1980 article by Mitchell Wand, based on the use of continuations.

Examples

Example A:
M = M since 99 ≤ 100
= M since 110 > 100
= M since 100 ≤ 100
= M since 111 > 100
= 91 since 101 > 100
Example B:
M = M
= M
= M
= M
= M
= M
= M
= M
= M
= M
= M
= M
.... Pattern continues increasing till M, M and M
= M since 111 > 100
= 91 since 101 > 100

Code

Here is an implementation of the nested-recursive algorithm in Lisp:

)
))

Here is an implementation of the nested-recursive algorithm in Haskell:

mc91 n
| n > 100 = n - 10
| otherwise = mc91 $ mc91 $ n + 11

Here is an implementation of the nested-recursive algorithm in OCaml:

let rec mc91 n =
if n > 100 then n - 10
else mc91

Here is an implementation of the tail-recursive algorithm in OCaml:

let mc91 n =
let rec aux n c =
if c = 0 then n
else if n > 100 then aux
else aux
in
aux n 1

Here is an implementation of the nested-recursive algorithm in Python:

def mc91 -> int:
"""McCarthy 91 function."""
if n > 100:
return n - 10
else:
return mc91

Here is an implementation of the nested-recursive algorithm in C:

int mc91

Here is an implementation of the tail-recursive algorithm in C:

int mc91
int mc91taux

Proof

Here is a proof that
which provides an equivalent non-recursive algorithm to compute.
For n > 100, equality follows from the definition of. For n ≤ 100, a strong induction downward from 100 can be used.
For 90 ≤ n ≤ 100,
M = M, by definition
= M, since n + 11 > 100
= M
So M = M = 91 for 90 ≤ n ≤ 100.
This can be used as base case.
For the induction step, let n ≤ 89 and assume M = 91 for all n < i ≤ 100, then
M = M, by definition
= M, by hypothesis, since n < n + 11 ≤ 100
= 91, by the base case.
This proves M = 91 for all n ≤ 100, including negative values.

Knuth's generalization

generalized the 91 function to include additional parameters. John Cowles developed a formal proof that Knuth's generalized function was total, using the ACL2 theorem prover.