EWD845

McCarthy’s 91-function: an unfortunate paradigm

McCarthy’s 91-function —see below— is an ingenious and at first sight baffling construction, which deserved all the attention it attracted when it became known. Unfortunately it also acquired the status of “difficult testcase” for any proposed theory or set of proof rules for recursively defined functions. This is unfortunate for two reasons. Firstly, this function can be dealt with —see below— by such thoroughly elementary means that it is doubtful whether it is a very good testcase; secondly, its contortions are of such a nature —see below— that any method of dealing with it shows more of those contortions that of the method that is supposed to be illustrated.

McCarthy’s 91-function is g, given by the following recursive definition

g(x) = if x > 100 ⇒ x - 10 ⫾ x ≤ 100 ⇒ g(g(x + 11)) fi

and one is asked to demonstrate that it equals f, given by

f(x) = if x > 101 ⇒ x - 10 ⫾ x ≤ 101 ⇒ 91 fi

Here we go!

  g(x)

definition of g

if x > 100 ⇒ x - 10 ⫾ x ≤ 100 ⇒ g(g(x + 11)) fi

splitting the first alternative and unfolding once in the second alternative

if x > 101 ⇒ x - 10
  ⫾ x = 101 ⇒ 91
  ⫾ x ≤ 100 ⇒ g(if x + 11 > 100 ⇒ x + 11 - 10
         ⫾ x + 11 ≤ 100 ⇒ g(g(x + 11 + 11)) fi)
  fi

splitting of the last alternative and simplification

if x > 101 ⇒ x - 10
  ⫾ x = 101 ⇒ 91
  ⫾ 89 < x ≤ 100 ⇒ g(x + 1)
  ⫾ x < 89 ⇒ g³(x + 22)
  fi

terminating tail-recursion of third alternative

if x > 101 ⇒ x - 10
  ⫾ x = 101 ⇒ 91
  ⫾ 89 < x ≤ 100 ⇒ g(101)
  ⫾ x ≤ 89 ⇒ g³(x + 22)
  fi

combination of second and third alternative and terminating tail-recursion of the last one

if x > 101 ⇒ x - 10
  ⫾ 89 < x ≤ 101 ⇒ 91
  ⫾ x ≤ 89 ⇒ g^{2n + 3}(y) for some n ≥ 0 and 89 < y ≤ 111
  fi

applying g once in the last alternative

if x > 101 ⇒ x - 10
  ⫾ 89 < x ≤ 101 ⇒ 91
  ⫾ x ≤ 89 ⇒ g^{2n + 2}(y) for some n ≥ 0 and 91 < y < 101
  fi

applying g another time in the last alternative

if x > 101 ⇒ x - 10
  ⫾ 89 < x ≤ 101 ⇒ 91
  ⫾ x ≤ 89 ⇒ g^{2n + 1}(91) for some n ≥ 0
  fi

since g(91) = 91, the last two can be combined

if x > 101 ⇒ x - 10
  ⫾ x ≤ 101 ⇒ 91
  fi

definition of f

  f(x)          Q.E.D.

That is all, in a long sequence of minute transformations. It is a winding argument that, of course, can be delivered in 57 varieties, but when you have seen one of them, you have seen them all. The 91-function is, as said, an ingenious construction, but it is an unfortunate paradigm since it leads to demonstrations that are both lengthy and boring.

I hope this is the last technical note in which the 91-function is treated.

transcribed by Jonathan David Arndt
revised 21-Jan-2020