マッカーシーの91関数のソースを表示

{{出典の明記|date=2022年12月10日 (土) 05:35 (UTC)}}
'''マッカーシーの91関数'''（[[英語|英]]: '''McCarthy 91 function'''）とは、[[離散数学]]における[[再帰呼び出し|再帰]]関数の一種であり、整数引数 ''n'' &le; 101 に対して 91 を返し、''n'' > 101 に対しては <math>n - 10</math> を返す。[[計算機科学|計算機科学者]][[ジョン・マッカーシー]]が考案した<ref>{{Cite web |url=https://mathworld.wolfram.com/McCarthy91-Function.html |title=McCarthy 91-Function -- from Wolfram MathWorld |access-date=2023年6月3日 |publisher=Wolfram Mathworld}}</ref>。

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

:<math>M(n)=\left\{\begin{matrix} n - 10, & \mbox{if }n > 100\mbox{ } \\ M(M(n+11)), & \mbox{if }n \le 100\mbox{ } \end{matrix}\right.</math>

例 A:

 M(99) = M(M(110))   99 &le; 100 であるため
       = M(100)      110 > 100 であるため
       = M(M(111))   100 &le; 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))))

<!-- And, here is an iterative implementation of the McCarthy 91 function written in [[C++]]: 

 int mccarthy(int n)
 {
     for (int c = 1; c != 0; ) {
         if (n > 100) {
             n = n - 10;
             c--;
         } else {
             n = n + 11;
             c++;
         }
     }
     return n;
 } -->

この関数が期待通りに動作することの証明は次のようになる。

90 &le; ''n'' &lt; 101 のとき、

 M(n) = M(M(n + 11))
      = M(n + 11 - 10)  なぜなら n >= 90 であるから n + 11 >= 101 となるため
      = M(n + 1)

従って 90 &le; ''n'' &lt; 101 のとき ''M''(''n'') = 91 である。

以上を基本として、11個の数のブロック毎に証明していく。''a'' &le; ''n'' &lt; ''a'' + 11 について ''M''(''n'') = 91 であるとする。そのとき ''a'' - 11 &le; ''n'' &lt; ''a'' となるような任意の ''n'' について、

 M(n) = M(M(n + 11))
      = M(91)  仮定から、a &le; n + 11 < a + 11 であるため
      = 91  基本ケースから

以上のように ''n'' をブロック単位で考えれば ''M''(''n'') = 91 であることが求められる。ブロック間に抜けているところはないので、''n'' &lt; 101 の場合常に ''M''(''n'') = 91 となる。また、''n'' = 101 の場合を特殊例として追加することもできる。

== 脚注 ==
{{reflist}}

{{DEFAULTSORT:まつかしの91かんすう}}
[[Category:離散数学]]
[[Category:数学に関する記事]]