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