マッカーシーの91関数
 | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。（2022年12月） |
マッカーシーの91関数（英: McCarthy 91 function）とは、離散数学における再帰関数の一種であり、整数引数 n ≤ 101 に対して 91 を返し、n > 101 に対しては を返す。計算機科学者ジョン・マッカーシーが考案した[1]。
マッカーシーの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 の場合を特殊例として追加することもできる。
- ^ “McCarthy 91-Function -- from Wolfram MathWorld”. Wolfram Mathworld. 2023年6月3日閲覧。
「McCarthy 91 function」の例文・使い方・用例・文例
- アメリカのすべての都市では緊急時には911に電話する
- 最初は1914年に建てられ、1945年に戦災を受けました。現在の駅は、元の姿に復元するために2012年に建て直されたものです。
- 彼のクラシックカーのコレクションには1914年モデルのブルーム型自動車が含まれている。
- ポルシェ911カブリオレ
- その講堂は1912年に建てられた。
- 1991年の証券不祥事は日本のビジネス界に深刻な損害を与えた。
- 私は1991年から1995年まで中国にいた。
- 第一次世界大戦は 1918 年に終わった.
- (在位1910‐36).
- 第 2 インターナショナル (1889‐1914).
- 第 3 インターナショナル (1919‐43).
- 彼は数字を取り違えて 91 を 19 と書いてしまった.
- トラブルのときには911に電話してください
- 1918年のフィッシャー法は、決定的に彼らの地位と賃金を上げた
- 1912年、遠洋定期船タイタニックは、その処女航海で沈んだ
- 1914年8月に、フランス、ドイツ、オーストリア、そして、ベルギー人の委員会のメンバー達が未来の平和を祝い共に乾杯したが、気の滅入る感傷的で小さな祝宴だった
- トルコ人は、1915年にアルメニア人を抹殺した
- 商務長官の職は1913年に設けられた
- 労働省長官の職は1913年に設けられた
- 1903年に創設されて1913年に2つの部に分割された前の管理部の代表
Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
- McCarthy 91 functionのページへのリンク
