{
  "id": "enwiki-001321323383",
  "slug": "mccarthy-91-function",
  "title": "McCarthy 91 function",
  "qid": "",
  "lead": "The McCarthy 91 function is a recursive function, defined by the computer scientist John McCarthy as a test case for formal verification within computer science. The McCarthy 91 function is defined as : M(n)=\\begin{cases} n - 10, & \\mbox{if }n > 100\\mbox{ } \\\\ M(M(n+11)), & \\mbox{if }n \\le 100\\mbox{ } \\end{cases} The results of evaluating the function are given by M(n) = 91 for all integer arguments n ≤ 100, and M(n) = n &minus; 10 for n &gt; 100. Indeed, the result of M(101) is also 91 (101 - 10 = 91). All results of M(n) after n = 101 are continually increasing by 1, e.g. M(102) = 92, M(103) = 93.",
  "body": "The McCarthy 91 function is a recursive function, defined by the computer scientist John McCarthy as a test case for formal verification within computer science. The McCarthy 91 function is defined as M(n)=\\begin{cases} n - 10, & \\mbox{if }n > 100\\mbox{ } \\\\ M(M(n+11)), & \\mbox{if }n \\le 100\\mbox{ } \\end{cases} The results of evaluating the function are given by M(n)&nbsp;=&nbsp;91 for all integer arguments n&nbsp;≤&nbsp;100, and M(n)&nbsp;=&nbsp;n&nbsp;&minus;&nbsp;10 for n &gt; 100. Indeed, the result of M(101) is also 91 (101 - 10 = 91). All results of M(n) after n = 101 are continually increasing by 1, e.g. M(102) = 92, M(103) = 93. ==History== The 91 function was introduced in papers published by Zohar Manna, Amir Pnueli and John McCarthy in 1970. These papers represented early developments towards the application of formal methods to program verification. The 91 function was chosen for being nested-recursive (contrasted with single recursion, such as defining f(n) by means of f(n-1) ). The example was popularized by Manna's book, Mathematical Theory of Computation (1974). As the field of Formal Methods advanced, this example appeared repeatedly in the research literature. In particular, it is viewed as a \"challenge problem\" for automated program verification. It is easier to reason about tail-recursive control flow, this is an equivalent (extensionally equal) definition: M_t(n)= M_t'(n,1) M_t'(n, c)=\\begin{cases} n, & \\mbox{if }c = 0\\\\ M_t'(n-10, c-1), & \\mbox{if }n > 100\\mbox{ and } c \\ne 0 \\\\ M_t'(n+11, c+1), & \\mbox{if }n \\le 100\\mbox{ and } c \\ne 0 \\end{cases} As one of the examples used to demonstrate such reasoning, Manna's book includes a tail-recursive algorithm equivalent to the nested-recursive 91 function. Many of the papers that report an \"automated verification\" (or termination proof) of the 91 function only handle the tail-recursive version. This is an equivalent mutually tail-recursive definition: M_{mt}(n)= M_{mt}'(n,0) M_{mt}'(n,c)=\\begin{cases} M_{mt}(n-10,c), & \\mbox{if }n > 100\\mbox{ } \\\\ M_{mt}'(n+11,c+1), & \\mbox{if }n \\le 100\\mbox{ } \\end{cases} M_{mt}(n,c)=\\begin{cases} n, & \\mbox{if }c = 0\\mbox{ } \\\\ M_{mt}'(n,c-1), & \\mbox{if }c \\ne 0\\mbox{ } \\end{cases} A formal derivation of the mutually tail-recursive version from the nested-recursive one was given in a 1980 article by Mitchell Wand, based on the use of continuations. ==Examples== Example A: M(99) = M(M(110)) since 99 ≤ 100 M(87) = M(M(98)) = 91 since 101 > 100 ==Code== Here is an implementation of the nested-recursive algorithm in Python: def mc91(n: int) -> int: if n > 100: return n - 10 else: return mc91(mc91(n + 11)) Here is an implementation of the tail-recursive algorithm in Python: def mc91(n: int) -> int: return mc91taux(n, 1) def mc91taux(n: int, c: int) -> int: if c == 0: return n elif n > 100: return mc91taux(n - 10, c - 1) else: return mc91taux(n + 11, c + 1) ==Proof== Here is a proof that the McCarthy 91 function M is equivalent to the non-recursive algorithm M' defined as: M'(n)=\\begin{cases} n - 10, & \\mbox{if }n > 100\\mbox{ } \\\\ 91, & \\mbox{if }n \\le 100\\mbox{ } \\end{cases} For n &gt; 100, the definitions of M' and M are the same. The equality therefore follows from the definition of M . For n ≤ 100, a strong induction downward from 100 can be used: For 90 ≤ n ≤ 100, M(n) = M(M(n + 11)), by definition This can be used to show M(n) = M(101) = 91 for 90 ≤ n ≤ 100: M(90) = M(91), M(n) = M(n + 1) was proven above M(n) = M(101) = 91 for 90 ≤ n ≤ 100 can be used as the base case of the induction. For the downward induction step, let n ≤ 89 and assume M(i) = 91 for all n &lt; i ≤ 100, then M(n) = M(M(n + 11)), by definition This proves M(n) = 91 for all n ≤ 100, including negative values.",
  "categories": [
    "106747104",
    "130110808",
    "20284999",
    "23118434",
    "23204091",
    "23603337",
    "23837581",
    "24745114",
    "25257581",
    "29176593",
    "36473759",
    "95814580"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1321323383",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1762724567.0,
  "claims": [
    {
      "id": 29521863,
      "subject_qid": "",
      "subject_slug": "mccarthy-91-function",
      "predicate": "publication date",
      "object_text": "1970",
      "object_num": 19700000.0,
      "object_unit": null,
      "polarity": 1,
      "qualifier": "",
      "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1321323383",
      "source_name": "Wikipedia",
      "source_tier": 3,
      "retrieved_at": 1792483437.9082477,
      "confidence": 0.95,
      "article_slug": "mccarthy-91-function",
      "span_start": 53,
      "span_end": 102
    }
  ],
  "contradictions": [],
  "confidence": 0.95,
  "csl": {
    "id": "enwiki-001321323383",
    "type": "webpage",
    "title": "McCarthy 91 function",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/mccarthy-91-function",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001321323383",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1321323383",
    "note": "Immutable snapshot enwiki-001321323383"
  }
}