McCarthy 91 function

Encyclopedia : M : MC : MCC : McCarthy 91 function

In discrete mathematics, the McCarthy 91 function is a recursive function which returns 91 for all integer arguments n ≤ 100 and returns [n - 10] for n > 100. It was conceived by computer scientist John McCarthy.

The McCarthy 91 function is defined as

[M(n)=\left\ n - 10, & \mboxn > 100\mbox \\ M(M(n+11)), & \mboxn \le 100\mbox \end\right.]

Examples:

M(99) = M(M(110)) since 99 ≤ 100
= M(100)    since 110 > 100
= M(M(111)) since 100 ≤ 100
= M(101)    since 111 > 100
= 91        since 101 > 100

M(87) = M(M(98))
= M(M(M(109)))
= M(M(99))
= M(M(M(110)))
= M(M(100))
= M(M(M(111)))
= M(M(101))
= M(91)
= M(M(102))
= M(92)
= M(M(103))
= M(93)
.... Pattern continues
= M(99)
(same as above proof)
= 91

Here is how John McCarthy may have written this function in Lisp, the language he invented:

(defun mc91 (n)
(cond ((< n 1) (error "Function only defined for positive values of n"))
((<= n 100) (mc91 (mc91 (+ n 11))))
(t (- n 10))))

Here is a proof that the function behaves as expected.

For 90 ≤ n < 101,

M(n) = M(M(n + 11))
= M(n + 11 - 10), since n >= 90 so n + 11 >= 101
= M(n + 1)

So M(n) = 91 for 90 ≤ n < 101.

We can use this as a base case for induction on blocks of 11 numbers, like so:

Assume that M(n) = 91 for a ≤ n < a + 11.

Then, for any n such that a - 11 ≤ n < a,

M(n) = M(M(n + 11))
= M(91), by hypothesis, since a ≤ n + 11 < a + 11
= 91, by the base case.

Now by induction M(n) = 91 for any n in such a block. There are no holes between the blocks, so M(n) = 91 for n < 101. We can also add n = 101 as a special case.

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.