マッカーシーの91関数

マッカーシーの91関数（英: McCarthy 91 function）とは、離散数学における再帰関数の一種であり、整数引数 "n" ≤ 101 に対して 91 を返し、"n" > 101 に対しては formula_1 を返す。計算機科学者ジョン・マッカーシーが考案した。
マッカーシーの91関数の定義は次の通り。
例 A:
 M(99) = M(M(110)) 99 ≤ 100 であるため
 = M(100) 110 > 100 であるため
 = M(M(111)) 100 ≤ 100 であるため
 = M(101) 111 > 100 であるため
 = 91 101 > 100 であるため
例 B:
 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)
 ... このパターンが続く
 = M(99)
 （以下、例 A と同じ）
 = 91
ジョン・マッカーシーはこれを、自身が開発したLISP言語で次のように書いた。
 (defun mc91 (n)
 (cond ((<= n 100) (mc91 (mc91 (+ n 11))))
 (t (- n 10))))
この関数が期待通りに動作することの証明は次のようになる。
90 ≤ "n" < 101 のとき、
 M(n) = M(M(n + 11))
 = M(n + 11 - 10) なぜなら n >= 90 であるから n + 11 >= 101 となるため
 = M(n + 1)
従って 90 ≤ "n" < 101 のとき "M"("n") = 91 である。
以上を基本として、11個の数のブロック毎に証明していく。"a" ≤ "n" < "a" + 11 について "M"("n") = 91 であるとする。そのとき "a" - 11 ≤ "n" < "a" となるような任意の "n" について、
 M(n) = M(M(n + 11))
 = M(91) 仮定から、a ≤ n + 11 < a + 11 であるため
 = 91 基本ケースから
以上のように "n" をブロック単位で考えれば "M"("n") = 91 であることが求められる。ブロック間に抜けているところはないので、"n" < 101 の場合常に "M"("n") = 91 となる。また、"n" = 101 の場合を特殊例として追加することもできる。