マッカーシーの91関数

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

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

脚注 

離散数学
数学に関する記事