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 ⇒ g3(x + 22)
  fi
terminating tail-recursion of third alternative
  if x > 101 ⇒ x - 10
  ⫾ x = 101 ⇒ 91
  ⫾ 89 < x ≤ 100 ⇒ g(101)
  ⫾ x ≤ 89 ⇒ g3(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 ⇒ g2n + 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 ⇒ g2n + 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 ⇒ g2n + 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.

Plataanstraat 5
5671 AL NUENEN
The Netherlands		 21 December 1983
prof.dr.Edsger W. Dijkstra
Burroughs Research Fellow