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