マッカーシーの91関数

マッカーシーの91関数（英: McCarthy 91 function）とは、離散数学における再帰関数の一種であり、整数引数 n ≤ 101 に対して 91 を返し、n > 101 に対しては $n-10$ を返す。計算機科学者ジョン・マッカーシーが考案した。

マッカーシーの91関数の定義は次の通り。

$M(n)=\left\{{\begin{matrix}n-10,&{\mbox{if }}n>100{\mbox{ }}\\M(M(n+11)),&{\mbox{if }}n\leq 100{\mbox{ }}\end{matrix}}\right.$

例 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 の場合を特殊例として追加することもできる。